Part4
2 Sum
ā: Check if a pair with given sum exists in Array
š§ :
1. Store the current element with index in hash map
2. while iterating through arrays, check whether curr - sum in hashmap
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, num in enumerate(nums):
if target - num in seen:
return [seen[target - num], i]
seen[num] = i
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut seen: HashMap<i32, i32> = HashMap::new();
for i in 0..nums.len() {
let ii: i32 = i as i32;
let req = target - nums[i];
if seen.contains_key(&req) {
return vec![seen[&req], ii];
}
seen.insert(nums[i], ii);
}
vec![]
}
}
4 Sum
ā: Find Quads that add up to a target value
š§ :
1. Sort the array and use 4 pointers.
2. Fix i and j pointers and put left and right pointers at the left and right end of remaining array
3. To avoid duplicate quads, while moving the pointers, move them only if they are not equal to their previous elements
4. If 4 elements sum is equal to target, store them. Else according to sum, move left and right pointers as elements are already sorted
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
res = []
n = len(nums)
nums.sort()
for i in range(n):
if i != 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n):
if j != i + 1 and nums[j] == nums[j - 1]:
continue
left, right = j + 1, n - 1
required_sum = target - nums[i] - nums[j]
while left < right:
if nums[left] + nums[right] < required_sum:
left += 1
elif nums[left] + nums[right] > required_sum:
right -= 1
else:
res.append([nums[i], nums[j], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
return res
(Another approach to avoid duplicates is storing them in set)
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
res = set()
n = len(nums)
nums.sort()
for i in range(n):
for j in range(i + 1, n):
left, right = j + 1, n - 1
required_sum = target - nums[i] - nums[j]
while left < right:
if nums[left] + nums[right] < required_sum:
left += 1
elif nums[left] + nums[right] > required_sum:
right -= 1
else:
res.add((nums[i], nums[j], nums[left], nums[right]))
left += 1
right -= 1
use std::collections::HashSet;
impl Solution {
pub fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
let mut nums = nums;
nums.sort();
let n = nums.len();
let mut res: HashSet<(i32, i32, i32, i32)> = HashSet::new();
for i in 0..n {
for j in i + 1..n {
let (mut l, mut r) = (j + 1, n - 1);
let req = target as i64 - nums[i] as i64 - nums[j] as i64;
while l < r {
if (nums[l] + nums[r]) as i64 == req {
res.insert((nums[i], nums[j], nums[l], nums[r]));
l += 1;
r -= 1;
} else if ((nums[l] + nums[r]) as i64) < req {
l += 1;
} else {
r -= 1;
}
}
}
}
let mut return_value: Vec<Vec<i32>> = vec![];
for (a, b, c, d) in res {
return_value.push(vec![a, b, c, d]);
}
return_value
}
}
Longest Consecutive Sequence
ā: You are given an array of āNā integers. You need to find the length of the longest sequence which contains the consecutive elements.
š§ :
O(NlogN) Solution
1. Sort the array
2. Find the consecutive sequence by iterating through array. (it cannot have same elements)
O(N) Solution
1. Store all the elements in set
2. For every element, search and count all the consecutive elements only if
a. It is start of sequence(curr-1 is not in set)
b. We will storing maximum sequence in a variable res. if curr + res is not present in set, that means the curr count itself is large sequence, again don't need to find the current sequence length
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
if n <= 1:
return n
res = 1
curr_count = 1
prev = nums[0]
for num in nums[1:]:
if prev + 1 == num:
curr_count += 1
prev = num
elif num == prev:
continue
else:
prev = num
res = max(res, curr_count)
curr_count = 1
return max(res, curr_count)
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
res = 0
temp = {i: 1 for i in nums}
for i in nums:
if i - 1 in temp or i + res not in temp:
continue
c = 1
e = i
while e + 1 in temp:
c += 1
e += 1
res = max(res, c)
return res
use std::cmp::max;
impl Solution {
pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
let mut nums = nums;
nums.sort();
let n = nums.len();
if n == 0 {
return 0;
}
let mut prev = nums[0];
let mut count = 1;
let mut res = 1;
for &num in &nums[1..] {
if num == prev {
continue;
} else if num == prev + 1 {
count += 1;
} else {
res = max(res, count);
count = 1;
}
prev = num;
}
max(res, count)
}
}
Longest SubArray with Zero Sum
ā: Given an array containing both positive and negative integers, we have to find the length of the longest subarray with the sum of all elements equal to zero.
š§ :
1. Store the prefix sum in hashmap with value as index
2. if we find the prefix sum again, then that part of array sum is zero
def solution(nums: list[int]) -> int:
d: dict[int, int] = {0: -1}
curr_sum = 0
res = 0
for i, num in enumerate(nums):
curr_sum += num
if curr_sum in d:
res = max(res, i - d[curr_sum])
else:
d[curr_sum] = i
return res
assert solution([9, -3, 3, -1, 6, -5]) == 5
assert solution([6, -2, 2, -8, 1, 7, 4, -10]) == 8
assert solution([1, 0, -5]) == 1
assert solution([1, 3, -5, 6, -2]) == 0
use std::cmp::max;
use std::collections::HashMap;
fn longest_subarray_with_zero_sum(nums: &Vec<i32>) -> i32 {
let mut d: HashMap<i32, i32> = HashMap::new();
d.insert(0, -1);
let mut sum = 0;
let mut res = 0;
for i in 0..nums.len() {
sum += nums[i];
if d.contains_key(&sum) {
res = max(res, i as i32 - d[&sum])
} else {
d.insert(sum, i as i32);
}
}
res
}
fn main() {
assert_eq!(
longest_subarray_with_zero_sum(&vec![9, -3, 3, -1, 6, -5]),
5
);
assert_eq!(
longest_subarray_with_zero_sum(&vec![6, -2, 2, -8, 1, 7, 4, -10]),
8
);
assert_eq!(longest_subarray_with_zero_sum(&vec![1, 0, -5]), 1);
assert_eq!(longest_subarray_with_zero_sum(&vec![1, 3, -5, 6, -2]), 0);
}
Count number of subarrays with given XOR K
Coming Soon
Longest Substring without repeating characters
ā: Given a String, find the length of longest substring without any repeating character.
š§ :
1. Store the seen elements in hashmap with its indexes
2. Once you encounter a seen element, compute the res by finding the gap b/w current index and seen index and reset left pointer to seen index plus 1
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
if s == "":
return 0
left = 0
seen = {}
res = 0
for i in range(n):
if s[i] in seen and seen[s[i]] >= left:
res = max(res, i - left)
left = seen[s[i]] + 1
seen[s[i]] = i
return max(res, i - left + 1)
use std::cmp::max;
use std::collections::HashMap;
impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let n = s.len();
if n == 0 {
return 0;
}
let mut seen: HashMap<char, usize> = HashMap::new();
let mut left = 0;
let mut res = 0;
for (i, ch) in s.chars().enumerate() {
if seen.contains_key(&ch) && seen[&ch] >= left {
res = max(res, i - left);
left = seen[&ch] + 1;
}
seen.insert(ch, i);
}
max(res, n - left) as i32
}
}