Search in fully rotated sorted 2D matrix

JavaView on GFG

Time: O(log(n*m))

Space: O(1)

Problem Overview

Search in fully rotated sorted matrix where element may be anywhere.

See our study guide for structured GFG and LeetCode practice.

Intuition

Search in fully rotated sorted matrix where element may be anywhere. Check each row or flatten.

Algorithm

1Since rotation breaks the staircase property, binary search each row independently.

Common Pitfalls

• Cannot use staircase search on fully rotated matrix. O(m log n) by binary searching each row.

Search in fully rotated sorted 2D matrix.java

Java

// Approach: Binary search for row candidate, then binary search within row.
// Time: O(log(n*m)) Space: O(1)
class Solution {
    public boolean searchMatrix(int[][] mat, int x) {
        int n = mat.length;
        int m = mat[0].length;
        int left = 0, right = n * m - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midVal = mat[mid / m][mid % m];
            if (midVal == x)
                return true;
            int leftVal = mat[left / m][left % m];
            int rightVal = mat[right / m][right % m];

            if (leftVal <= midVal) {
                if (x >= leftVal && x < midVal)
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                if (x > midVal && x <= rightVal)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return false;
    }
}

Was this solution helpful?