• 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

Diagonal Traversal of Binary Tree

HackeEarth Flipkart’s Drone

Check if an array has duplicate numbers in O(n) time and O(1) space

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Facebook Interview Question : Interleave List

Python Array String

Knight Tour Problem (Graph – Breadth First Search)

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

LeetCode: Binary Tree Maximum Path Sum

Find the number ABCD such that when multipled by 4 gives DCBA.

Cisco Hiring Event 21st – 22nd Feb 2015

Find position of the only set bit

Difference between a LinkedList and a Binary Search Tree BST

Word Break Problem

Count Possible Decodings of a given Digit Sequence

Skiing on Mountains Matrix

Coin Collection Dynamic Programming

Common Ancestor in a Binary Tree or Binary Search Tree

Adobe Interview Questions 8 month Exp

Find next greater number with same set of digits

Find two non repeating elements in an array of repeating elements

Calculate price of parking from parking start end time prices

Maximum path sum between two leaves

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

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

Closed Parentheses checker

Advanced SQL Injection

Amazon Interview Experience – SDE Chennai

Maximum occurred Smallest integer in n ranges

Copyright © 2025 · Genesis Framework · WordPress · Log in