Home » Matrix-Backtrack » 2D Matrix Search

2D Matrix Search

Given an n x n matrix, where every row and column is sorted in increasing order. Given a number x, how to decide whether this x is in the matrix. The designed algorithm should have linear time complexity.

1) Start with top right element
2) Loop: compare this element e with x
….i) if they are equal then return its position
…ii) e < x then move it to down (if out of bound of matrix then break return false)
..iii) e > x then move it to left (if out of bound of matrix then break return false)
3) repeat the i), ii) and iii) till you find element or returned false


import java.util.*;

public class MatrixwithMax1
{

/* A function to find the index of first index of 1 in a boolean array arr[] */
public static int first(int arr[], int low, int high)
{
 if(high >= low)
 {
 // get the middle index
 int mid = low + (high - low)/2;

 // check if the element at middle index is first 1
 if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
 return mid;

 // if the element is 0, recur for right side
 else if (arr[mid] == 0)
 return first(arr, (mid + 1), high);

 else // If element is not first 1, recur for left side
 return first(arr, low, (mid -1));
 }
 return -1;
}

// The main function that returns index of row with maximum number of 1s.
public static int rowWithMax1s(int mat[][])
{
 int max_row_index = 0, max = -1; // Initialize max values

 // Traverse for each row and count number of 1s by finding the index
 // of first 1
 int i, index;
 for (i = 0; i < R; i++)
 {
 index = first (mat[i], 0, C-1);
 if (index != -1 && C-index > max)
 {
 max = C - index;
 max_row_index = i;
 }
 }

 return max_row_index;
}

 public static void main(String[] args)
 {
 int mat[][] = { {0, 0, 0, 1},
 {0, 1, 1, 1},
 {1, 1, 1, 1},
 {0, 0, 0, 0}
 };

 System.out.println("Index of row with maximum 1s is %d \n", rowWithMax1s(mat));

 }

 }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: