Enumerate Right Maintain Left¶

Table of Contents¶

1. Two Sum¶

LeetCode | LeetCode CH (Easy)
Tags: array, hash table
Return the indices of the two numbers such that they add up to a specific target.
Approach: Use a hashmap to store the indices of the numbers.
Time Complexity: O(n)
Space Complexity: O(n)

1. Two Sum - Python Solution

from typing import List


def twoSum(nums: List[int], target: int) -> List[int]:
    hashmap = {}  # val: idx

    for idx, val in enumerate(nums):
        if (target - val) in hashmap:
            return [hashmap[target - val], idx]

        hashmap[val] = idx


if __name__ == "__main__":
    nums = [2, 7, 11, 15]
    target = 9
    assert twoSum(nums, target) == [0, 1]

1. Two Sum - C++ Solution

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> hashmap;

    for (size_t i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];

        if (hashmap.find(complement) != hashmap.end()) {
            return {hashmap[complement], (int)i};
        }
        hashmap[nums[i]] = (int)i;
    }

    return {-1, -1};
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(nums, target);
    cout << result[0] << ", " << result[1] << endl;
    return 0;
}

1512. Number of Good Pairs¶

LeetCode | LeetCode CH (Easy)
Tags: array, hash table, math, counting

1512. Number of Good Pairs - Python Solution

from collections import defaultdict
from typing import List


# Hash
def numIdenticalPairs(nums: List[int]) -> int:
    res = 0
    counts = defaultdict(int)  # num: count

    for num in nums:
        res += counts[num]
        counts[num] += 1

    return res


nums = [1, 2, 3, 1, 1, 3]
print(numIdenticalPairs(nums))  # 4

2001. Number of Pairs of Interchangeable Rectangles¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, math, counting, number theory

2001. Number of Pairs of Interchangeable Rectangles - Python Solution

from collections import defaultdict
from typing import List


# Hash
def interchangeableRectangles(rectangles: List[List[int]]) -> int:
    res = 0
    counts = defaultdict(int)

    for w, h in rectangles:
        ratio = w / h
        res += counts[ratio]
        counts[ratio] += 1

    return res


rectangles = [[4, 8], [3, 6], [10, 20], [15, 30]]
print(interchangeableRectangles(rectangles))  # 6

219. Contains Duplicate II¶

LeetCode | LeetCode CH (Easy)
Tags: array, hash table, sliding window

219. Contains Duplicate II - Python Solution

from typing import List


# Hash
def containsNearbyDuplicateHash(nums: List[int], k: int) -> bool:
    hashmap = {}  # num: last index

    for idx, num in enumerate(nums):
        if num in hashmap:
            if idx - hashmap[num] <= k:
                return True

        hashmap[num] = idx

    return False


# Sliding window - Fixed
def containsNearbyDuplicateWindow(nums: List[int], k: int) -> bool:
    window = set()
    left = 0

    for right in range(len(nums)):
        if right - left > k:
            window.remove(nums[left])
            left += 1
        if nums[right] in window:
            return True
        window.add(nums[right])

    return False


nums = [1, 2, 3, 1]
k = 3
print(containsNearbyDuplicateHash(nums, k))  # True
print(containsNearbyDuplicateWindow(nums, k))  # True

121. Best Time to Buy and Sell Stock¶

LeetCode | LeetCode CH (Easy)
Tags: array, dynamic programming
Return the maximum profit that can be achieved from buying on one day and selling on another day.

121. Best Time to Buy and Sell Stock - Python Solution

from typing import List


# Brute Force
def maxProfitBF(prices: List[int]) -> int:
    max_profit = 0
    n = len(prices)
    for i in range(n):
        for j in range(i + 1, n):
            max_profit = max(max_profit, prices[j] - prices[i])

    return max_profit


# DP
def maxProfitDP(prices: List[int]) -> int:
    dp = [[0] * 2 for _ in range(len(prices))]
    dp[0][0] = -prices[0]  # buy
    dp[0][1] = 0  # sell

    for i in range(1, len(prices)):
        dp[i][0] = max(dp[i - 1][0], -prices[i])  # the lowest price to buy
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])

    return dp[-1][1]


# Greedy
def maxProfitGreedy(prices: List[int]) -> int:
    max_profit = 0
    seen_min = prices[0]

    for i in range(1, len(prices)):
        max_profit = max(max_profit, prices[i] - seen_min)
        seen_min = min(seen_min, prices[i])

    return max_profit


# Fast Slow Pointers
def maxProfitFS(prices: List[int]) -> int:
    max_profit = 0
    slow, fast = 0, 1

    while fast < len(prices):
        if prices[fast] > prices[slow]:
            max_profit = max(max_profit, prices[fast] - prices[slow])
        else:
            slow = fast
        fast += 1

    return max_profit


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# | Brute Force|  O(n^2)|  O(1)   |
# | DP         |  O(n)  |  O(n)   |
# | Greedy     |  O(n)  |  O(1)   |
# | Fast Slow  |  O(n)  |  O(1)   |
# |------------|--------|---------|


prices = [7, 1, 5, 3, 6, 4]
print(maxProfitBF(prices))  # 5
print(maxProfitDP(prices))  # 5
print(maxProfitGreedy(prices))  # 5
print(maxProfitFS(prices))  # 5

121. Best Time to Buy and Sell Stock - C++ Solution

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        if (prices.size() <= 1)
            return 0;

        int seen_min = prices[0];
        int res = 0;

        for (int &price : prices)
        {
            res = max(res, price - seen_min);
            seen_min = min(seen_min, price);
        }
        return res;
    }
};

int main()
{
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    Solution obj;
    cout << obj.maxProfit(prices) << endl;
    return 0;
}

624. Maximum Distance in Arrays¶

LeetCode | LeetCode CH (Medium)
Tags: array, greedy

624. Maximum Distance in Arrays - Python Solution

from typing import List


# Array
def maxDistance(arrays: List[List[int]]) -> int:
    mn, mx = float("inf"), float("-inf")
    res = 0

    for arr in arrays:
        res = max(res, arr[-1] - mn, mx - arr[0])
        mn = min(mn, arr[0])
        mx = max(mx, arr[-1])

    return res


arrays = [[1, 2, 3], [4, 5], [1, 2, 3]]
print(maxDistance(arrays))  # 4

2815. Max Pair Sum in an Array¶

LeetCode | LeetCode CH (Easy)
Tags: array, hash table

2815. Max Pair Sum in an Array - Python Solution

from collections import defaultdict
from typing import List


# Hash
def maxSumHash(nums: List[int]) -> int:
    def find(num):
        res = 0
        while num != 0:
            num, carry = divmod(num, 10)
            res = max(res, carry)
        return res

    freqs = defaultdict(list)

    for num in nums:
        x = find(num)
        freqs[x].append(num)

    res = -1
    for vals in freqs.values():
        if len(vals) > 1:
            vals = sorted(vals, reverse=True)
            res = max(res, sum(vals[:2]))

    return res


# Array
def maxSumArray(nums: List[int]) -> int:
    res = -1
    max_val = [float("-inf") for _ in range(10)]

    for num in nums:
        maxDigit = max(map(int, str(num)))
        res = max(res, num + max_val[maxDigit])
        max_val[maxDigit] = max(max_val[maxDigit], num)

    return res


nums = [2536, 1613, 3366, 162]
print(maxSumHash(nums))  # 5902
print(maxSumArray(nums))  # 5902

2342. Max Sum of a Pair With Equal Sum of Digits¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, sorting, heap priority queue

2342. Max Sum of a Pair With Equal Sum of Digits - Python Solution

from typing import List


# Enumerate Right Maintain Left
def maximumSum(nums: List[int]) -> int:
    def digits_sum(num):
        res = 0
        while num:
            num, carry = divmod(num, 10)
            res += carry
        return res

    hashmap = {}  # digit sum: largest num
    res = -1

    for num in nums:
        ds = digits_sum(num)

        if ds not in hashmap:
            hashmap[ds] = num
        else:
            res = max(res, num + hashmap[ds])
            hashmap[ds] = max(hashmap[ds], num)

    return res


nums = [18, 43, 36, 13, 7]
print(maximumSum(nums))  # 54

1679. Max Number of K-Sum Pairs¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, two pointers, sorting

1679. Max Number of K-Sum Pairs - Python Solution

from collections import defaultdict
from typing import List


# Enumerate Right Maintain Left
def maxOperations(nums: List[int], k: int) -> int:
    counts = defaultdict(int)

    res = 0
    for num in nums:
        if num >= k:
            continue

        j = k - num
        if j in counts:
            res += 1
            counts[j] -= 1
            if counts[j] == 0:
                del counts[j]
        else:
            counts[num] += 1

    return res


if __name__ == "__main__":
    assert maxOperations([1, 2, 3, 4], 5) == 2
    assert maxOperations([3, 1, 3, 4, 3], 6) == 1

2260. Minimum Consecutive Cards to Pick Up¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, sliding window

2260. Minimum Consecutive Cards to Pick Up - Python Solution

from typing import List


# Enumerate Right Maintain Left
def minimumCardPickup(cards: List[int]) -> int:
    n = len(cards)
    res = n + 1
    last = {}

    for idx, card in enumerate(cards):
        if card in last:
            res = min(res, idx - last[card] + 1)
        last[card] = idx

    return res if res != n + 1 else -1


if __name__ == "__main__":
    assert minimumCardPickup([1, 2, 3, 4, 5]) == -1
    assert minimumCardPickup([1, 2, 3, 2, 3]) == 3

1010. Pairs of Songs With Total Durations Divisible by 60¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, counting

1010. Pairs of Songs With Total Durations Divisible by 60 - Python Solution

from collections import defaultdict
from typing import List


# Enumerate Right Maintain Left
def numPairsDivisibleBy60(time: List[int]) -> int:
    if not time or len(time) < 2:
        return 0

    count = defaultdict(int)
    res = 0
    time = [t % 60 for t in time]

    for t in time:
        if t == 0:
            res += count[0]
        else:
            res += count[60 - t]
        count[t] += 1

    return res


if __name__ == "__main__":
    assert numPairsDivisibleBy60([30, 20, 150, 100, 40]) == 3
    assert numPairsDivisibleBy60([60, 60, 60]) == 3
    assert numPairsDivisibleBy60([10, 50, 30, 20, 40]) == 2

3185. Count Pairs That Form a Complete Day II¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, counting

2506. Count Pairs Of Similar Strings¶

LeetCode | LeetCode CH (Easy)
Tags: array, hash table, string, bit manipulation, counting

2748. Number of Beautiful Pairs¶

LeetCode | LeetCode CH (Easy)
Tags: array, hash table, math, counting, number theory

2874. Maximum Value of an Ordered Triplet II¶

LeetCode | LeetCode CH (Medium)
Tags: array

2874. Maximum Value of an Ordered Triplet II - Python Solution

from typing import List


def maximumTripletValue(nums: List[int]) -> int:
    res = 0
    max_diff = 0
    max_prev = 0

    for num in nums:
        res = max(res, max_diff * num)
        max_diff = max(max_diff, max_prev - num)
        max_prev = max(max_prev, num)

    return res


if __name__ == "__main__":
    nums = [12, 6, 1, 2, 7]
    print(maximumTripletValue(nums))  # 77

1014. Best Sightseeing Pair¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming

1814. Count Nice Pairs in an Array¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, math, counting

2905. Find Indices With Index and Value Difference II¶

LeetCode | LeetCode CH (Medium)
Tags: array, two pointers

1031. Maximum Sum of Two Non-Overlapping Subarrays¶

LeetCode | LeetCode CH (Medium)
Tags: array, dynamic programming, sliding window

2555. Maximize Win From Two Segments¶

LeetCode | LeetCode CH (Medium)
Tags: array, binary search, sliding window

2555. Maximize Win From Two Segments - Python Solution

from typing import List


# Sliding Window - Variable
def maximizeWin(prizePositions: List[int], k: int) -> int:
    n = len(prizePositions)

    if 2 * k >= prizePositions[-1] - prizePositions[0]:
        return n

    ans = left = 0
    mx = [0] * (n + 1)

    for right, p in enumerate(prizePositions):
        while p - prizePositions[left] > k:
            left += 1
        ans = max(ans, mx[left] + right - left + 1)
        mx[right + 1] = max(mx[right], right - left + 1)

    return ans


prizePositions = [1, 1, 2, 2, 3, 3, 5]
k = 2
print(maximizeWin(prizePositions, k))  # 7

1995. Count Special Quadruplets¶

LeetCode | LeetCode CH (Easy)
Tags: array, hash table, enumeration

3404. Count Special Subsequences¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, math, enumeration

3267. Count Almost Equal Pairs II¶

LeetCode | LeetCode CH (Hard)
Tags: array, hash table, sorting, counting, enumeration

1214. Two Sum BSTs¶

LeetCode | LeetCode CH (Medium)
Tags: two pointers, binary search, stack, tree, depth first search, binary search tree, binary tree

2964. Number of Divisible Triplet Sums¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table

2441. Largest Positive Integer That Exists With Its Negative¶

LeetCode | LeetCode CH (Easy)
Tags: array, hash table, two pointers, sorting

454. 4Sum II¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table
Return the number of tuples (i, j, k, l) such that A[i] + B[j] + C[k] + D[l] == 0.

454. 4Sum II - Python Solution

from collections import defaultdict
from typing import List


def fourSumCount(
    nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]
) -> int:

    sumAB = defaultdict(int)
    result = 0

    for i in nums1:
        for j in nums2:
            sumAB[i + j] += 1

    for i in nums3:
        for j in nums4:
            if -(i + j) in sumAB:
                result += sumAB[-(i + j)]

    return result


nums1 = [1, 2]
nums2 = [-2, -1]
nums3 = [-1, 2]
nums4 = [0, 2]
print(fourSumCount(nums1, nums2, nums3, nums4))  # 2

3371. Identify the Largest Outlier in an Array¶

LeetCode | LeetCode CH (Medium)
Tags: array, hash table, counting, enumeration