amazon sde2 reject july

In a 2d matrix N*N. Make all col and rows 0 where at least one 0 is found.
1 1 1    .     1 0 1
1 0 1  =>      0 0 0
1 1 1     .    1 0 1

0 1 2 0        0 0 0 0
1 2 3 4  =>    0 2 3 0
5 4 3 2        0 4 3 0

Note: matrix is having only positive integers

## My approach
I gave two approaches:
1.
  - Do iteration once. save cols and rows in two sets. [O(N*N)]
  - Then iterate onece again and look if that col is present in set COLSET  OR row is present in ROWSET. If yes then make it Zero(0) . O(N*N)
  - Total complexity O(N*N)

 2. Other is without using extra space
  - first make all zeros as -1 so that we keep track of which cell has already zero and on with we have placed.
  - Then go one by one on each cell and look if this row and col has at least one -1 present.
      - if yes then mark it Zero(0)
 - at last iterate once again to make all -1s 0 again
 - Total complexity is O(n*n*n)  N cube in worst case. [because for each cell we are looking row and col]

Then he said do it less than O n cube complexity that too without using extra space.
I could not think of anything.  Brain Jammed






Find Next Bigger element on Right side of an. element in array
and -1 if no found
Example:
[13 2 1 4 5 6 10]

[-1 4 4 5 6 10-1]

## My approach
By this time my brain was already jammed and stuck on first question. He moved on to second question.
Here i explained Brute force first then moved on to find better soln.
After trying to fit all Data structured that i know of I was back to -  somehow store intermediate answers into an array.
Came up with a temporary solution but it was still ON*N in worst case.

Note: Had I solved this question before I could easily do it.  It uses stack  geeksforgeeks.org/next-greater-element/ :facepalm: