• 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

Subset Sum Problem Dynamic programming

BFS (Breath First Search)

Templates in C++

SAP Hiring Off-Campus General Aptitude

flattens 2 D linked list to a single sorted link list

How Radix sort works

Edit Distance ( Dynamic Programming )

Naurki.com Security Breach

FizzBuzz Solution C C++

Find the element that appears once others appears thrice

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

Find Percentage of Words matching in Two Strings

Introduction To Number Theory ( Part 1 )

Find if two rectangles overlap

SAP Off Campus Hiring_ March 2015 Verbal Skills

Maximum path sum between two leaves

Linked List V/S Binary Search Tree

BlueStone E-commerce Interview Experience

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 ?

Client Server C program

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

Find min element in Sorted Rotated Array (With Duplicates)

Fibonacci Hashing & Fastest Hashtable

Common Ancestor in a Binary Tree or Binary Search Tree

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

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

HackeEarth Flipkart’s Drone

Print vertical sum of all the axis in the given binary tree

Doubly linked list

Count Possible Decodings of a given Digit Sequence

Copyright © 2025 · Genesis Framework · WordPress · Log in