DILI #15: More Lit Codes with LeetCodes !!!!

WASSAPPPPP! I have decided doing LeetCodes is too LIT 🔥🔥🔥! So here's some more problems that I found interesting!

Problem #1: 3 Sum

This problem in a way is easier than it's predecessor: 2 Sum. Because the answer doesn't require the index, but rather digits in the array that sum to 0. So, I instantly thought of sorting the array, and just do a "selective bruteforcing" using the Two Pointer Technique.

We need to meet the requirement: a + b + c = 0. So, by choose the first digit as "a" and increment the left pointer by one when the sum is negative, and reduce the right pointer by one when the sum is positive - as the array is sorted. With this we can quickly find all the sets that sums to 0.

Though, we can make it BETTER 💪💪💪! If the 2 digits adjacent to each other are the same, we would just be repeating what we were doing in the last iteration. So that's a loss of time! And if that sums to 0 as well, the output array would have 2 of the same answers, and that is said by the problem designer to be exclude. So we need to skip to the next index whenever that happens.
Source Code:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int head = 0;
        int n = nums.size();
        vector<vector<int>> ans;

        if(n < 3) return ans;
        for(int i = 0; i < n - 2; i++){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i - 1] == nums[i]) continue;

            int left = i + 1;
            int right = n - 1;
            while(left < right){
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else{
                    ans.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1])
                        left++;
                    left++;
                    while (left < right && nums[right] == nums[right - 1])
                        right--;
                    right--;
                }
            }
        }
        return ans;
    }
};

Problem #2: Find Minimum in Rotated Sorted Array

This problem baffled me when I first read it,... until I reached the "O(log n)" line. To find "target" digit in an array in O(log n), I instantly thought of Binary Search,... or you can see it as the headline in NeetCode:).

Anyways, as the array is already sorted in ascending order but "rotated", it's just Binary Search with a twist. The act of rotating is just splitting the array into 2 ascending subarrays. So, knowing whether we are in the left ascending part or the right ascending part would be a great help. So, how should we know ? Well, if our "middle" digit is larger than our leftmost digit in the array, we must be in the left part. And if not, we on the right part.

The end goal is to find the smallest digit in that array, so where is it abstractly. Well, it should be in the right part as the array is rotated! So, if we're on the left part, we would want to move right to reach our smallest digit, else we would want to move left to go to the smallest digit in our right side.

Source Code:

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        int ans = nums[0];

        while(left <= right){
            if(nums[left] < nums[right]){
                ans = min(ans, nums[left]);
                break;
            }

            int mid = (left + right)/2;
            ans = min(ans,nums[mid]);
            if(nums[mid] >= nums[left]){
                left = mid + 1;
            }
            else right = mid - 1;
        }
        return ans;
    }
};

That's all the time I have for today! Only two, I know, how lazy of me! But these two puzzles really bring out the beauty of 2 of the most staple techniques in programming. I had time to do the second part of Problem #2 which instead of finding the smallest number, I need to search for a target number. It's a great problem to help you learn how to ultilized the thing you know, Problem #2, and also how to split bigger problem into smaller ones! And that's it! Have a great week until next time!

REFERENCES:
LeetCode
NeetCode