Contains Duplicate II (LeetCode 219)
Given an integer array
numsand an integerk, returntrueif there are two distinct indicesiandjin the array such thatnums[i] == nums[j]andabs(i - j) <= k.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
import java.util.*;
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
return true;
}
map.put(nums[i], i);
}
return false;
}
}class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
d = {}
for i in range(len(nums)):
if nums[i] in d and i - d[nums[i]] <= k:
return True
d[nums[i]] = i
return False| Type | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
- Approach: Use a HashMap to store the last seen index of each element. Iterate through the array; if the current element is already in the map and the difference between the current index and its stored index is
<= k, return true. Otherwise, update the index in the map. - Dry run (nums = [1,2,3,1], k = 3):
- i=0, num=1: map is empty. map = {1: 0}
- i=1, num=2: map = {1: 0, 2: 1}
- i=2, num=3: map = {1: 0, 2: 1, 3: 2}
- i=3, num=1: 1 is in map. 3 - map.get(1) = 3 - 0 = 3 <= 3 -> return true.
Minimum Size Subarray Sum (LeetCode 209)
209. Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
1 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^4
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
curr_sum = 0
min_len = float('inf')
for right in range(len(nums)):
curr_sum += nums[right]
while curr_sum >= target:
min_len = min(min_len, right - left + 1)
curr_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0| Type | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
- Approach: Sliding window. Expand the right pointer to increase the sum. When the sum meets or exceeds the target, shrink from the left to find the minimum window, then continue expanding right.
- Dry run (target = 7, nums = [2,3,1,2,4,3]):
- right=0: sum=2. < 7.
- right=1: sum=5. < 7.
- right=2: sum=6. < 7.
- right=3: sum=8. >= 7 → minLen=4. Shrink: sum=6, left=1. < 7.
- right=4: sum=10. >= 7 → minLen=4. Shrink: sum=7, left=2 → minLen=3. Shrink: sum=6, left=3. < 7.
- right=5: sum=9. >= 7 → minLen=3. Shrink: sum=7, left=4 → minLen=2. Shrink: sum=3, left=5. < 7.
- Return minLen = 2.
Longest Substring Without Repeating Characters (LeetCode 3)
3. Longest Substring Without Repeating Characters
Given a string
s, find the length of the longest substring without duplicate characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
class Solution {
public int lengthOfLongestSubstring(String s) {
int l = 0, r = 0;
int n = s.length() ;
int m = 0;
HashSet<Character> set = new HashSet<>();
while (r < n) {
char c = s.charAt(r);
while (set.contains(c)) {
set.remove(s.charAt(l));
l++;
}
set.add(c);
m = Math.max(m, r - l + 1);
r++;
}
return m;
}
}class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l = r = 0
n = len(s)
m = 0
seen = set()
while r < n:
c = s[r]
while c in seen:
seen.remove(s[l])
l += 1
seen.add(c)
m = max(m, r - l + 1)
r += 1
return m| Type | Value |
|---|---|
| Time | O(n) |
| Space | O(k) |
- Approach: Sliding window with HashSet. Expand right pointer, shrink left when duplicate found. k = size of character set.
- Dry run (s = "abcabcbb"):
- r=0: add 'a', set={a}, m=1
- r=1: add 'b', set={a,b}, m=2
- r=2: add 'c', set={a,b,c}, m=3
- r=3: 'a' in set, remove 'a', l=1, add 'a', set={b,c,a}, m=3
- r=4: 'b' in set, remove 'b', l=2, add 'b', set={c,a,b}, m=3
- Continue... final m=3
Variant: Return the Actual Substring
class Solution {
public String longestSubstring(String s) {
int l = 0, r = 0;
int n = s.length();
int maxLen = 0;
int start = 0; // track start of best substring
HashSet<Character> set = new HashSet<>();
while (r < n) {
char c = s.charAt(r);
while (set.contains(c)) {
set.remove(s.charAt(l));
l++;
}
set.add(c);
if (r - l + 1 > maxLen) {
maxLen = r - l + 1;
start = l; // store start index
}
r++;
}
return s.substring(start, start + maxLen);
}
}class Solution:
def longestSubstring(self, s: str) -> str:
l = r = 0
n = len(s)
max_len = 0
start = 0
seen = set()
while r < n:
c = s[r]
while c in seen:
seen.remove(s[l])
l += 1
seen.add(c)
if r - l + 1 > max_len:
max_len = r - l + 1
start = l
r += 1
return s[start:start + max_len]| Type | Value |
|---|---|
| Time | O(n) |
| Space | O(k) |
- Dry run (s = "abcabcbb"):
- Same as above, but tracks
startindex when maxLen updates - Final: start=0, maxLen=3 → return "abc"
- Same as above, but tracks
Longest Repeating Character Replacement (LeetCode 424)
424. Longest Repeating Character Replacement
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example 1:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.
class Solution {
public int characterReplacement(String s, int k) {
int max = 0;
int ans = 0;
int left = 0;
int freq[] = new int[26];
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
freq[ch - 'A']++;
max = Math.max(max, freq[ch - 'A']);
while ((right - left + 1) - max > k) {
freq[s.charAt(left) - 'A']--;
left++;
}
ans = Math.max(right - left + 1, ans);
}
return ans;
}
}class Solution:
def characterReplacement(self, s: str, k: int) -> int:
max_freq = 0
ans = 0
left = 0
freq = [0] * 26
for right in range(len(s)):
idx = ord(s[right]) - ord('A')
freq[idx] += 1
max_freq = max(max_freq, freq[idx])
while (right - left + 1) - max_freq > k:
freq[ord(s[left]) - ord('A')] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans| Type | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
- Approach: Sliding window. Maintain a frequency array and track the count of the most frequent character in the window. If the number of characters to replace (
window_size - max_freq) exceedsk, shrink the window from the left. - Dry run (s = "AABABBA", k = 1):
- Expand window. At window "AABA" (right=3): max_freq=3 ('A'), replacements=1 ≤ k → valid, ans=4.
- Continues... final ans=4.