PROBLEM LINK:
DIFFICULTY:
Cake-Walk
PREREQUISITES:
None
PROBLEM:
Given an R x C grid of numbers, find out a number which is the smallest number in its row and the largest number in its column or report that no such number exists.
QUICK EXPLANATION:
Do an exhaustive search - for each cell in the grid, check if it satisfies the given conditions or not.
DETAILED EXPLANATION:
Approach 1:
The naivest approach would be to iterate over all the cells and for each cell check
if it is the smallest cell in its row and the largest cell in its column.
This approach takes time O( RC (R+C))
Approach 2:
Though previous approach is sufficient to get accepted, one can be a little smarter.
Let’s consider that at some point of time your program examines (a, b). At that time
we find out the smallest element of the row a and the largest element of column
b. When we examine (a, b+1), we’d again find out the smallest element of row a
and thus repeat the computation. It suggests that we find out the smallest
element of each row and the largest element of each column only once and store
it. This precomputation takes O(RC) time. Once it has been done, we could judge
if a given cell is desired answer or not in constant time looking at pre computed
values. Hence even this step is O(RC).
So total this approach takes O(RC) time.
SETTER’S SOLUTION:
Can be found here.
TESTER’S SOLUTION:
Can be found here.