• 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

Sequence Finder Dynamic Programming

flattens 2 D linked list to a single sorted link list

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

VMWare Openings

Amazon Interview On-Campus For Internship – 1

Print Power Set of a Set

Test Cases for Round Function

Level order traversal in Spiral form

Memory Efficient LinkedList

BlueStone E-commerce Interview Experience

Skiing on Mountains Matrix

Find next greater number with same set of digits

LeetCode : Word Search

SAP Interview Questions

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

Wrong Directions given find minimum moves so that he can reach to the destination

Given a string, find the first character which is non-repetitive

SAP Off Campus Hiring_ March 2015 Sample Questions

Add Sub Multiply very large number stored as string

Given a float number convert it into the string WITHOUT using any inbuilt Function

CodeChef Code SGARDEN

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

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

Python List

Flipkart Set 1 On Campus with Answers

Regular Expression Matching

Advanced SQL Injection

Urban Ladder Written Test.

SAP Off Campus Hiring_ March 2015 Verbal Skills

Find position of the only set bit

Copyright © 2025 · Genesis Framework · WordPress · Log in