View the matrix as a single sorted sequence and apply standard binary search.

Search a 2D Matrix

easy

Acceptance: 57%

Binary Search

You are given an m-by-n matrix of integers where each row is sorted in ascending order and the first value of each row exceeds the last value of the row above it. Given a target integer, determine whether it exists in the matrix. Your solution should run in O(log(m*n)) time.

Examples

Example 1:

Input:matrix = [[1,4,7],[10,13,16],[19,22,25]], target = 13

Output:true

Explanation: 13 appears in the second row.

Example 2:

Input:matrix = [[1,4,7],[10,13,16],[19,22,25]], target = 14

Output:false

Explanation: 14 is not present in the matrix.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Search a 2D Matrix

Examples

Hints

Related Problems