• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Search element in a matrix with all rows and columns in sorted order

August 27, 2014 by Dhaval Dave

Given a matrix containing unique numbers in which all rows and columns are in sorted order.
And You have to search an element output its location row,column number .
If no such element the just print ”-1 -1”.

Example:
5  5                               //size of matrix
 -10   -5   -3    4     9     //matrix
-6     -2     0    5    10
-4     -1     1    6    12
  2      3     7    8    13
100  120 130 140 150
3   // number of elements to be search
0   //element to be search
-2 //element to be search
170 //element to be search
Output:

1 2  // location of 0
1 1 // location of -2
-1 -1 //location of 170
Solution:
We can use normal brute force solution which can give O(m*n) time complexity.
By using binary search we can further reduce the complexity by(m*log(n))
But here is the simplest and optimal solution which takes O(n+m) complexity which we can say if n=m then O(2n)=O(n) or similar order if n!=m

#include <iostream>
#include <stdio.h>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <math.h>
using namespacestd;
int A[1009][1009];
int main()
{
      int n,m;
      scanf(“%d%d”,&n,&m);
      for(int i=0;i<n;i++)
      {
            for(int j=0;j<m;j++)
            {
                  scanf(“%d”,&A[i][j]);
            }
      }
      int t;
      cin>>t;
      while(t–)
      {
            int p;
            cin>>p;
            int i=0,j=m–1;
            bool f=false;
             while(i<n && j>=0)
            {
                  if(A[i][j]==p)
                  {
                        cout<<i<<” “<<j<<endl;
                        f=true;
                        break;
                  }
                  else if(A[i][j]>p)
                  {
                        j–;
                  }
                  else if(A[i][j]<p)
                  {
                        i++;
                  }     
            }
            if(f==false) cout<<“-1 -1”<<endl;
      }
      return 0;
}


Article and code by Dheeraj 

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: 2d matrix, Binary Search

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Convert number to words java

Connect n ropes with minimum cost

Difference between a LinkedList and a Binary Search Tree BST

Find Pythagorean Triplets in an array in O(N)

Word Break Problem

Number of Islands BFS/DFS

Maximum occurred Smallest integer in n ranges

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

C++ OOPs Part2

Find min element in Sorted Rotated Array (With Duplicates)

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Maximum difference between two elements s.t larger element appears after the smaller number

Calculate price of parking from parking start end time prices

Get K Max and Delete K Max in stream of incoming integers

Test Cases for Round Function

Length of the longest substring without repeating characters

Trapping Rain Water

Longest Increasing Subsequence

Count number of ways to reach a given score in a game

Implement LRU Cache

Find loop in Singly linked list

Find if a binary tree is height balanced ?

Edit Distance ( Dynamic Programming )

Serialise Deserialise N-ary Tree

Flipkart Set 1 On Campus with Answers

Maximum of all subarrays of size k

Find the element that appears once others appears thrice

Check Binary Tree is Binary Search Tree or not

Find the kth number with prime factors 3, 5 and 7

Find the smallest window in a string containing all characters of another string

Copyright © 2025 · Genesis Framework · WordPress · Log in