Tasks

Two Pointers

April 2023

Index	Name	Number	Difficulty	Link
1	Container With Most Water	11	Medium	https://leetcode.com/problems/container-with-most-water/
2	Two Sum II - Input array is sorted	167	Easy	https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
3	3Sum	15	Medium	https://leetcode.com/problems/3sum/
4	Longest Palindromic Substring	5	Medium	https://leetcode.com/problems/longest-palindromic-substring/
5	Trapping Rain Water	42	Hard	https://leetcode.com/problems/trapping-rain-water/
6	Remove Duplicates from Sorted Array	26	Easy	https://leetcode.com/problems/remove-duplicates-from-sorted-array/
7	Squares of a Sorted Array	977	Easy	https://leetcode.com/problems/squares-of-a-sorted-array/
8	Valid Palindrome II	680	Easy	https://leetcode.com/problems/valid-palindrome-ii/
9	Minimum Window Substring	76	Hard	https://leetcode.com/problems/minimum-window-substring/
10	Sort Colors	75	Medium	https://leetcode.com/problems/sort-colors/

// 11. Container With Most Water

// Time: O(n) | Space: O(1)
var maxArea = function(height) {
    let max = 0;
    let left = 0;
    let right = height.length - 1;
    while (left < right) {
        const h = Math.min(height[left], height[right]);
        const range = right - left;
        const value = h * range;
        max = Math.max(max, value);
        height[left] < height[right] ? left++ : right--;
    }
    return max;
};

/*
Two Pointers
-------------------------
range = (right - left);
currentHeight = Math.min(height[right], height[left]);
result = Math.max(result, range * currentHeight);

Move left++ if right height is bigger.
Move right-- if left height is bigger.
-------------------------
Time: O(n) | Space: O(1)
*/

// 167. Two Sum II - Input Array Is Sorted

// Time: O(n) | Space: O(1) 
var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;
    while (left < right) {
        const diff = target - numbers[left] - numbers[right];
        if (diff === 0) {
            return [++left, ++right];
        }
        if (diff < 0) {
            right--;
        } else {
            left++;
        }
    }
    return [];
};

/*
Two Pointers
-------------------------
1. Itrate over sortaed array.
2. Check if sum matches the target (diff is used to avoid max int overflow)
3. If matches -> return 1-based indexes.
4. If no matches -> return an empty array.
-------------------------
Time: O(n) | Space: O(1)
*/

// 15. 3Sum

// Time: O(n^2) | Space: O(n)
var threeSum = function(nums) {
    if (nums.length < 3) {
        return [];
    }
    nums.sort((a, b) => a - b);
    let result = [];
    let unique = {};
    
    for (let i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
        let k = nums.length - 1;
        for (let j = i + 1; j < k; j++) {
            let sum = nums[i] + nums[j] + nums[k];
            let key = 'unique_' + nums[i] + nums[j] + nums[k];
            if (sum === 0 && !unique[key]) {
                result.push([nums[i], nums[j], nums[k]]);
                unique[key] = true;
            } else if (sum > 0) {
                k--;
                j--;
            }
        }
    }
    return result;
};

/*
Two Pointers
------------------------
Sort array
Go from i = 0 to length - 2.
    Go from j = i + 1 to k = length - 1.
        If sum === 0 && !unique[key] -> result.push. And save unique key.
        Else if sum > 0 -> k--, j--.
Return result.
------------------------
Time: O(n^2) | Space: O(n)
*/

// 5. Longest Palindromic Substring

// Time: O(n) | Space: O(n)
var longestPalindrome = function(s) {
    let res = '';
    const checkVariant = (left, right) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            const len = right - left + 1;
            if (len > res.length) {
                res = s.substring(left, right + 1);
            }
            left--;
            right++;
        }
    };
    for (let i = 0; i < s.length; i++) {
        checkVariant(i, i);
        checkVariant(i, i + 1);
    }
    return res;
};

/*
Two Pointers
---------------------
1. Iterate over string;
2. Try to echo (go left and right) from every char;
3. Keep the longest result.
---------------------
Time: O(n^2) | Space: O(n)
*/

// 42. Trapping Rain Water

// Time: O(n) | Space: O(1)
var trap = function(height) {
    let leftMax = 0;
    let rightMax = 0;
    let totalWater = 0;
    let left = 0;
    let right = height.length - 1;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] > leftMax) {
                leftMax = height[left];
            } else {
                totalWater += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] > rightMax) {
                rightMax = height[right];
            } else {
                totalWater += rightMax - height[right];
            }
            right--;
        }
    }
    return totalWater;
};

/*
Two Pointers
------------------------
1. Go in cycle while left < right.
2. Remember the boundary height (leftMax) from left.
3. Remember the boundary height (rightMax) from right.
After we have leftMax/rightMax -> they are our boundaries and possible to contain water.
4. If next left/right is less then max left/right -> diff is trapped water.
------------------------
Time: O(n) | Space: O(1)
*/

// 26. Remove Duplicates from Sorted Array

// Time: O(n) | Space: O(1)
var removeDuplicates = function(nums) {
    if (!nums.length) {
        return 0;
    }
    let left = 0;
    let right = 1;
    while (right < nums.length) {
        if (nums[left] !== nums[right]) {
            left++;
            nums[left] = nums[right];
        }
        right++;
    }
    return left + 1;
};

/*
Two Pointers
------------------------
1. Iterate over with right pointer.
2. If left != right -> replace next after left with right.
3. Return left index + 1 (length of unique).
------------------------
Time: O(n) | Space: O(1)
*/

// 977. Squares of a Sorted Array

// Time: O(n) | Space: O(n)
var sortedSquares = function(nums) {
    let left = 0;
    let right = nums.length - 1;
    let res = [];
    
    while (left <= right) {
        let l = nums[left] ** 2;
        let r = nums[right] ** 2;
        if (l < r) {
            res.push(r);
            right--;
        } else {
            res.push(l);
            left++;
        }
    }
    
    return res.reverse();
};

/*
Two Pointers
------------------------
1. Get squares for left and right.
2. Push bigger to the new array.
3. Return reverted new.
------------------------
Time: O(n) | Space: O(n)
*/

// 680. Valid Palindrome II

// Time: O(n) | Space: O(1)
var validPalindrome = function(s) {
    const check = (left, right, lives) => {
        while (left < right) {
            if (s[left] !== s[right]) {
                if (!lives) {
                    return false;
                }
                return check(left + 1, right) || check(left, right - 1); 
            }
            left++;
            right--;
        }
        return true;
    }
    return check(0, s.length - 1, 1);
};

/*
Two Pointers
------------------------
1. Go from left and right.
2. If left !== right -> try left + 1 and right - 1.
3. If not equal again -> return false.
4. Return true at the end. 
------------------------
Time: O(n) | Space: O(1)
*/

// 76. Minimum Window Substring

// Time: O(n + m) | Space: O(m)
var minWindow = function(s, t) {
    const frequency = t.split('').reduce((acc, char) => {
        acc[char] = ++acc[char] || 1;
        return acc;
    }, {});
    let left = 0;
    let right = 0;
    let count = t.length;
    let minWindowLength = Infinity;
    let minWindowStartIndex = 0;
    while (right < s.length) {
        if (s[right] in frequency) {
            if (frequency[s[right]] > 0) {
                count--;
            }
            frequency[s[right]]--;
        }
        right++;
        while (count === 0) {
            if ((right - left) < minWindowLength) {
                minWindowLength = right - left;
                minWindowStartIndex = left;
            }
            if (s[left] in frequency) {
                frequency[s[left]]++;
                if (frequency[s[left]] > 0) {
                    count++;
                }
            }
            left++;
        }
    }
    return minWindowLength === Infinity 
        ? '' 
        : s.substring(minWindowStartIndex, minWindowStartIndex + minWindowLength);
};

/*
Two Pointers
------------------------
1. Create frequency map.
2. Left and right pointers to zero.
3. Count to t.length.
4. minWindowLength to Infinity and minWindowStartIndex to 0 for the result.
5. Iterate from right to s.length.
6. If s[right] in frequency -> we need to check this char.
6.1. If frequency[s[right]] > 0 -> we should count it as a part of the window
6.1.1. count-- -> reduce count -> we are closer to window to be found.
6.2. frequency[s[right]]-- -> minus one char to be checked in the string.
6.3. right++ -> go to the next char in the string.
6.4. while (count === 0) -> we found the window and now we are searching for the min solution.
6.4.1. if (right - left < minWindowLength) -> current solution is closer to the searched result.
6.4.1.1 save current window length and start index.
6.4.2. if s[left] in frequency -> this char might affect count.
6.4.2.1. frequency[s[left]]++ -> keep frequency actual to be able to move left pointer.
6.4.2.2. if (frequency[s[left]] > 0) -> increase count. The window is broken and we will return to our right pointer.
6.4.3. left++ -> move right pointer after all checks.
7. If minWindowLength is still Infinity -> no results found -> return empty line.
8. If not Infinity -> return substring from minWindowStartIndex to index + window length. 
------------------------
Time: O(n + m) -> n for [s] iteration and m for [t] frequency map creation.
Space: O(m) -> to initialize frequency map.
*/

// 75. Sort Colors

// Time: O(n) | Space: O(1)
var sortColors = function(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    for (let i = 0; i <= right; i++) {
        if (nums[i] === 0) {
            [nums[left], nums[i]] = [nums[i], nums[left]];
            left++;
        }
        if (nums[i] === 2) {
            [nums[right], nums[i]] = [nums[i], nums[right]];
            right--;
            i--;
        }
    }
    
    return nums;
};

/*
Two Pointers
------------------------
If i element is 0 -> swap with left. Left++;
At the same iteration -> if current element is 2 
    -> swap with right. Right++, i-- (because we need to check i element again).
If i > right -> All next elements are 2. 
Return result.

[2,0,1] i=0, left=0, right=2.
[1,0,2] i=0, left=0, right=1.
[1,0,2] i=1, left=0, right=1. *
[0,1,2] i=2, left=1, right=1.

If i < right -> after first iteration i === right, but we need to swap left.
That's why i <= right.
------------------------
Time: O(n) | Space: O(1)
*/