is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
As the matrix is sorted by rows and columns, take any element, its top and left element will be less than the element and right and bottom element will be greater than the element. lets assume the element is a. If a is removed from the matrix, we will check left and top. Let us assume left is greater than top. If we put left in place of a,
left<a and a<right => left<right, which maintains the row wise sorting.
as a > left, bottom > a => bottom > left
and we already assumed that left>top
So these two equation proves that column wise sorting is also maintained. Similar equations will arise if top is greater than left and we replace the vacant place with top. So we can replace the removed element with the greater of top and left. and then continue the process to the next removed place till there is nothing more to remove. So this rearrange occurs in an N*M matrix in O(N+M) complexity.
Now to solve the original problem we just remove the right, bottom element k times and rearrange after every removal. As the right, bottom element is highest in the matrix, after removing k-1 times we can find the kth largest element in that position.
The total complexity will become O(K(M+N))
In an N*N matrix it is O(K(2N)) = O(KN)
Code
- Vivek October 08, 2014