Enumerate Right Maintain Left¶
Table of Contents¶
- 1. Two Sum (Easy)
- 1512. Number of Good Pairs (Easy)
- 2001. Number of Pairs of Interchangeable Rectangles (Medium)
- 219. Contains Duplicate II (Easy)
- 121. Best Time to Buy and Sell Stock (Easy)
- 624. Maximum Distance in Arrays (Medium)
- 2815. Max Pair Sum in an Array (Easy)
- 2342. Max Sum of a Pair With Equal Sum of Digits (Medium)
- 1679. Max Number of K-Sum Pairs (Medium)
- 2260. Minimum Consecutive Cards to Pick Up (Medium)
- 1010. Pairs of Songs With Total Durations Divisible by 60 (Medium)
- 3185. Count Pairs That Form a Complete Day II (Medium)
- 2506. Count Pairs Of Similar Strings (Easy)
- 2748. Number of Beautiful Pairs (Easy)
- 2874. Maximum Value of an Ordered Triplet II (Medium)
- 1014. Best Sightseeing Pair (Medium)
- 1814. Count Nice Pairs in an Array (Medium)
- 2905. Find Indices With Index and Value Difference II (Medium)
- 1031. Maximum Sum of Two Non-Overlapping Subarrays (Medium)
- 2555. Maximize Win From Two Segments (Medium)
- 1995. Count Special Quadruplets (Easy)
- 3404. Count Special Subsequences (Medium)
- 3267. Count Almost Equal Pairs II (Hard)
- 1214. Two Sum BSTs (Medium) 👑
- 2964. Number of Divisible Triplet Sums (Medium) 👑
- 2441. Largest Positive Integer That Exists With Its Negative (Easy)
- 454. 4Sum II (Medium)
- 3371. Identify the Largest Outlier in an Array (Medium)
1. Two Sum¶
"""
- 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¶
2001. Number of Pairs of Interchangeable Rectangles¶
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¶
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¶
"""
- 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 <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¶
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¶
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¶
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¶
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¶
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¶
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¶
2506. Count Pairs Of Similar Strings¶
2748. Number of Beautiful Pairs¶
2874. Maximum Value of an Ordered Triplet II¶
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¶
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¶
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¶
1031. Maximum Sum of Two Non-Overlapping Subarrays¶
2555. Maximize Win From Two Segments¶
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¶
3404. Count Special Subsequences¶
3267. Count Almost Equal Pairs II¶
1214. Two Sum BSTs¶
-
Tags: Two Pointers, Binary Search, Stack, Tree, Depth First Search, Binary Search Tree, Binary Tree
2964. Number of Divisible Triplet Sums¶
2441. Largest Positive Integer That Exists With Its Negative¶
454. 4Sum II¶
"""
- 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