View All num of num See all Photos Twitter about.twitter.com Engaged Employer Overview Reviews Salaries Interviews Jobs Photos Benefits 269 Reviews 637 Salaries 323 Interviews 458 Jobs Follow Add Interview Follow Add Interview Interview Question Software Engineer Interview San Francisco, CA Twitter Given an array with all elements sorted on each individual row and column find the K-th smallest one Tags: See more , See less 8 Answer Add Tags Answer Interview Answer 4 Answers ▲ 2 ▼ Top left is the smallest one, obviously. Insert that, along with (0, 0), into a min heap.while less than k elements have been popped: pop the smallest element. Say it's coordinates are (i, j) Insert (i+1, j), (i, j+1) into the min heap. These are the possible next smallest numbers.The element at the root of the min-heap is the k-th smallest element now. Jigsaw on Feb 2, 2013 ▲ 2 ▼ Treat every row in the matrix as a separate stream of numbers.Merge the streams in an ordered way while decrementing k. When k is zero, your current element is the one in question. bg on Mar 4, 2013 ▲ 1 ▼ Walk through the matrix starting (0, 0).The comparisons happen between bottom and right values.If the right value is smaller than bottom, go to the bottom.If bottom is smaller than right, go right.Count every time you make a move.Do this until counter == K or you reach end of matrix. deveffort on Jul 5, 2013 ▲ 0 ▼ The key feature of such a matrix is: The element at (m,n) should be the largest one in the sub matrix (0,0,m,n). So, the search should start from (0,N), then do zig-zag search based on the above feature. Jun on Jan 8, 2014 Interviews > Software Engineer > Twitter Add Answers or Comments To comment on this, Sign In or Sign Up.