Enumerate Right Maintain Left¶

Table of Contents¶

1. Two Sum¶

LeetCode | 力扣
Tags: Array, Hash Table

PythonCPP

"""
- 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)
"""

from typing import List


def two_sum(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

    return []


def test_two_sum():
    assert two_sum([2, 7, 11, 15], 9) == [0, 1]
    assert two_sum([3, 2, 4], 6) == [1, 2]
    assert two_sum([3, 3], 6) == [0, 1]
    assert two_sum([1, 2, 3, 4, 5], 10) == []
    assert two_sum([-1, -2, -3, -4, -5], -8) == [2, 4]

#include <cassert>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
   public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;

        for (size_t i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if (map.find(diff) != map.end()) {
                return {map[diff], (int)i};
            }
            map[nums[i]] = (int)i;
        }
        return {-1, -1};
    }
};

int main() {
    Solution solution;
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = solution.twoSum(nums, target);
    assert((result == vector<int>{0, 1}));
    return 0;
}

1512. Number of Good Pairs¶

LeetCode | 力扣
Tags: Array, Hash Table, Math, Counting

Python

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 | 力扣
Tags: Array, Hash Table, Math, Counting, Number Theory

Python

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 | 力扣
Tags: Array, Hash Table, Sliding Window

PythonCPP

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

#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
   public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> last;

        for (size_t i = 0; i < nums.size(); i++) {
            int num = nums[i];
            if (last.contains(num) && ((int)i - last[num] <= k)) return true;
            last[num] = i;
        }
        return false;
    }
    bool containsNearbyDuplicateSlidingWindow(vector<int>& nums, int k) {
        unordered_set<int> window;

        for (size_t i = 0; i < nums.size(); i++) {
            if (window.contains(nums[i])) return true;
            window.insert(nums[i]);

            if ((int)i - k >= 0) {
                window.erase(nums[i - k]);
            }
        }
        return false;
    }
};

int main() {
    Solution solution;
    vector<int> nums = {1, 2, 3, 1};
    assert(solution.containsNearbyDuplicate(nums, 3));
    assert(solution.containsNearbyDuplicateSlidingWindow(nums, 3));
    return 0;
}

121. Best Time to Buy and Sell Stock¶

LeetCode | 力扣
Tags: Array, Dynamic Programming

PythonCPP

"""
-   Return the maximum profit that can be achieved from buying on one day and selling on another day.
"""

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

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

class Solution {
   public:
    int maxProfitMemo(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.maxProfitMemo(prices) << endl;
    return 0;
}

624. Maximum Distance in Arrays¶

LeetCode | 力扣
Tags: Array, Greedy

Python

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 | 力扣
Tags: Array, Hash Table

Python

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 | 力扣
Tags: Array, Hash Table, Sorting, Heap Priority Queue

Python

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 | 力扣
Tags: Array, Hash Table, Two Pointers, Sorting

Python

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 | 力扣
Tags: Array, Hash Table, Sliding Window

Python

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 | 力扣
Tags: Array, Hash Table, Counting

Python

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 | 力扣
Tags: Array, Hash Table, Counting

2506. Count Pairs Of Similar Strings¶

LeetCode | 力扣
Tags: Array, Hash Table, String, Bit Manipulation, Counting

2748. Number of Beautiful Pairs¶

LeetCode | 力扣
Tags: Array, Hash Table, Math, Counting, Number Theory

2874. Maximum Value of an Ordered Triplet II¶

LeetCode | 力扣
Tags: Array

Python

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 | 力扣
Tags: Array, Dynamic Programming

Python

from typing import List


# Enumeate Right Maintain Left
def maxScoreSightseeingPair(values: List[int]) -> int:
    max_i = values[0] + 0
    res = 0

    for j in range(1, len(values)):
        res = max(res, max_i + values[j] - j)
        max_i = max(max_i, values[j] + j)

    return res


if __name__ == "__main__":
    assert maxScoreSightseeingPair([8, 1, 5, 2, 6]) == 11
    assert maxScoreSightseeingPair([1, 2]) == 2
    assert maxScoreSightseeingPair([1, 3, 5]) == 7
    assert maxScoreSightseeingPair([1, 2, 3, 4, 5]) == 8

1814. Count Nice Pairs in an Array¶

LeetCode | 力扣
Tags: Array, Hash Table, Math, Counting

Python

from collections import defaultdict
from typing import List


# Enumerate Right Maintain Left
def countNicePairs(nums: List[int]) -> int:
    rev = lambda n: int(str(n)[::-1])
    cnt = defaultdict(int)
    MOD = 10**9 + 7
    res = 0

    for num in nums:
        cnt[num - rev(num)] += 1

    for i in cnt.values():
        res += i * (i - 1) // 2  # math.comb(i, 2)

    return res % MOD


if __name__ == "__main__":
    assert countNicePairs([42, 11, 1, 97]) == 2
    assert countNicePairs([13, 10, 35, 24, 76]) == 4
    assert countNicePairs([100, 200, 300]) == 0
    assert countNicePairs([123, 321, 456, 654]) == 2
    assert countNicePairs([12, 21, 34, 43]) == 2

2905. Find Indices With Index and Value Difference II¶

LeetCode | 力扣
Tags: Array, Two Pointers

1031. Maximum Sum of Two Non-Overlapping Subarrays¶

LeetCode | 力扣
Tags: Array, Dynamic Programming, Sliding Window

2555. Maximize Win From Two Segments¶

LeetCode | 力扣
Tags: Array, Binary Search, Sliding Window

Python

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 | 力扣
Tags: Array, Hash Table, Enumeration

3404. Count Special Subsequences¶

LeetCode | 力扣
Tags: Array, Hash Table, Math, Enumeration

3267. Count Almost Equal Pairs II¶

LeetCode | 力扣
Tags: Array, Hash Table, Sorting, Counting, Enumeration

1214. Two Sum BSTs 👑¶

LeetCode | 力扣
Tags: Two Pointers, Binary Search, Stack, Tree, Depth First Search, Binary Search Tree, Binary Tree

2964. Number of Divisible Triplet Sums 👑¶

LeetCode | 力扣
Tags: Array, Hash Table

2441. Largest Positive Integer That Exists With Its Negative¶

LeetCode | 力扣
Tags: Array, Hash Table, Two Pointers, Sorting

454. 4Sum II¶

LeetCode | 力扣
Tags: Array, Hash Table

Python

"""
-   Return the number of tuples `(i, j, k, l)` such that `A[i] + B[j] + C[k] + D[l] == 0`.
"""

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 | 力扣
Tags: Array, Hash Table, Counting, Enumeration