004. Median of Two Sorted Arrays

Difficulty: Hard

Frequency: N/A

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), total = m + n;
        if (total % 2 == 1) return findK(nums1, 0, m, nums2, 0, n, total / 2 + 1);
        else return 0.5 * (findK(nums1, 0, m, nums2, 0, n, total / 2) +
            findK(nums1, 0, m, nums2, 0, n, total / 2 + 1));
        
    }
    int findK(vector<int>& nums1, int start1, int m, vector<int>& nums2, int start2, int n, int k) {
        if (m > n) return findK(nums2, start2, n, nums1, start1, m, k);
        if (m == 0) return nums2[start2 + k - 1];
        if (k == 1) return min(nums1[start1], nums2[start2]);
        int a = min(k / 2, m);
        int b = k - a;
        if (nums1[start1 + a - 1] <= nums2[start2 + b - 1]) return findK(nums1, start1 + a, m - a, nums2, start2, n, k - a);
        else return findK(nums1, start1, m, nums2, start2 + b, n - b, k - b);
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

240. Search a 2D Matrix II

Difficulty: Medium

Frequency: N/A

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.

For 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.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()) return false;
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) return true;
            else if (matrix[i][j] < target) i++;
            else j--;
        }
        return false;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

302. (Locked)Smallest Rectangle Enclosing Black Pixels

Difficulty: Medium

Frequency: N/A

An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

For example, given the following image:

[
“0010”,
“0110”,
“0100”
]
and x = 0, y = 2,
Return 6.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int minArea(vector<vector<char>> &iImage, int x, int y) {
        int m = iImage.size(), n = iImage[0].size();
        int top = searchRows(0, x, 0, n, true);
        int bottom = searchRows(x + 1, m, 0, n, false);
        int left = searchColumns(0, y, top, bottom, true);
        int right = searchColumns(y + 1, n, top, bottom, false);
        return (bottom - top) * (right - left);
    }
    int searchRows(int i, int j, int low, int high, bool opt) {
        while (i < j) {
            int k = low, med = i + (j - i) / 2;
            while (k < high && iImage[med][k] == '0') k++;
            if (k < high == opt) j = med;
            else i = med + 1;
        }
        return i;
    }
    int searchColumns(int i, int j, int low, int high, bool opt) {
        while (i < j) {
            int k = low, med = i + (j - i) / 2;
            while (k < high && iImage[k][med] == '0') k++;
            if (k < high == opt) j = med;
            else i = med + 1;
        }
        return i;
    }
}

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

275. H-Index II

Difficulty: Medium

Frequency: N/A

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int hIndex(vector<int>& citations) {
        if (citations.empty()) return 0;
        int n = citations.size(), lo = 0, hi = n - 1, med;
        while (lo <= hi) {
            med = lo + (hi - lo) / 2;
            if (citations[med] >= n - med) hi = med - 1;
            else lo = med + 1;
        }
        return n - lo;
    }
};


Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

074. Search a 2D Matrix

Difficulty: Medium

Frequency: N/A

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 from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()) return false;
        int m = matrix.size(), n = matrix[0].size();
        int lo = 0, hi = m - 1, med;
        while (lo < hi) {
            med = lo + (hi - lo + 1) / 2;
            if (matrix [med][0] > target) hi = med - 1;
            else lo = med;
        }
        int row = lo;
        lo = 0, hi = n - 1;
        while (lo < hi) {
            med = lo + (hi - lo + 1) / 2;
            if (matrix[row][med] > target) hi = med - 1;
            else lo = med;
        }
        return matrix[row][lo] == target ? true : false;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

081. Search in Rotated Sorted Array II

Difficulty: Medium

Frequency: N/A

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if (nums.size() == 1) return nums[0] == target ? true : false;
        int first = nums[0], lo = 1, hi = nums.size() - 1, med;
        while (nums[lo] == first && lo < nums.size() - 1) lo++;
        while (lo < hi) {
            med = lo + (hi - lo) / 2;
            if (nums[med] > first) lo = med + 1;
            else hi = med;
        }
        int pivot;
        if (first < nums[lo]) pivot = 0;
        else pivot = lo;
        if (nums[pivot] == target) return true;
        else if (target >= first && target >= nums[pivot] && pivot != 0) {
            lo = 0;
            hi = pivot;
        } else {
            lo = pivot;
            hi = nums.size() - 1;
        }
        while (lo < hi) {
            med = lo + (hi - lo) / 2;
            if (nums[med] == target) return true;
            else if (nums[med] > target) hi = med - 1;
            else lo = med + 1;
        }
        return target == nums[lo] ? true : false;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

033. Search in Rotated Sorted Array

Difficulty: Hard

Frequency: N/A

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.


My solution:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 1) return nums[0] == target ? 0 : -1;
        int first = nums[0], lo = 1, hi = nums.size() - 1, med;
        while (lo < hi) {
            med = lo + (hi - lo) / 2;
            if (nums[med] > first) lo = med + 1;
            else hi = med;
        }
        int pivot;
        if (first < nums[lo]) pivot = 0;
        else pivot = lo;
        if (nums[pivot] == target) return pivot;
        else if (target >= first && target >= nums[pivot] && pivot != 0) {
            lo = 0;
            hi = pivot;
        } else {
            lo = pivot;
            hi = nums.size() - 1;
        }
        while (lo < hi) {
            med = lo + (hi - lo) / 2;
            if (nums[med] == target) return med;
            else if (nums[med] > target) hi = med - 1;
            else lo = med + 1;
        }
        return target == nums[lo] ? lo : -1;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: