Search a 2D Matrix II

-
Problem is here: https://leetcode.com/problems/search-a-2d-matrix-ii/description/

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.
Example:
Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.
The trick is actually to start the search from the top right corner: if the target is equal to that cell, great, otherwise either move to the left or down for a total of O(m+n)-time and no extra space. Cheers, Boris.


public class Solution
{
 public bool SearchMatrix(int[,] matrix, int target)
 {
  if (matrix == null || matrix.GetLength(0) == 0 || matrix.GetLength(1) == 0) return false;

  int R = matrix.GetLength(0);
  int C = matrix.GetLength(1);

  int r = 0;
  int c = C - 1;
  while (r < R && c >= 0)
  {
   if (matrix[r, c] == target) return true;
   else if (matrix[r, c] > target) c--;
   else r++;
  }

  return false;
 }
}

Comments

  1. TarasDecember 22, 2018 at 8:40 PM

    I had this question on my very first interview with Microsoft and looks like we have almost identical solutions :)

    class Solution {
    public:
    bool searchMatrix(vector>& matrix, int target) {
    if (matrix.empty()) return false;
    int row = 0;
    int column = matrix[0].size()-1;
    while (row < matrix.size() && column >= 0) {
    int current_value = matrix[row][column];
    if (current_value == target) {
    return true;
    } else if (target < current_value) {
    column -= 1;
    } else {
    row += 1;
    }
    }
    return false;
    }
    };

    Cheers,
    Taras

    ReplyDelete
  2. Boris VasilenkoDecember 22, 2018 at 8:51 PM

    Cool! I’m torn about this question, it does seem a little tricky to me, although once you get the solution, it does look intuitive and clever

    ReplyDelete
    Replies
    1. TarasDecember 22, 2018 at 8:54 PM

      agreed, it's also a bit tricky since "sorted" keyword immediately triggers desire to use binary search :)

      Delete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more