Part2
Rotate Matrix
❓: Given a matrix, your task is to rotate the matrix 90 degrees clockwise.
# Using extra memory approach
def method(matrix):
"""
logic - i,j = j,n-i-1
"""
n = len(matrix)
res = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
res[j][n - i - 1] = matrix[i][j]
return res
# Better approach without using extra memory
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
1. Transpose the matrix
2. Reverse each row
"""
for i in range(len(matrix)):
for j in range(i + 1, len(matrix[0])):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(len(matrix)):
matrix[i] = matrix[i][::-1]
return matrix
impl Solution {
pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
let n = matrix.len();
let m = matrix[0].len();
for i in 0..n {
for j in i + 1..m {
let temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for i in 0..n {
matrix[i].reverse();
}
}
}
Merge Overlapping Sub Intervals
❓: Given an array of intervals, merge all the overlapping intervals and return an array of non-overlapping intervals.
class Solution:
def merge(self, nums: List[List[int]]) -> List[List[int]]:
"""
1. Sort the list
2. Create res list
3. Iterate through list and compare the item with the last item of res to check if merging is possible
4. If possible, update the last item of res, else add current item to res
"""
nums.sort()
res = [nums[0]]
for i in range(1, len(nums)):
if res[-1][-1] >= nums[i][0]:
res[-1] = [res[-1][0], max(res[-1][1], nums[i][1])]
else:
res.append(nums[i])
return res
use std::cmp::max;
impl Solution {
pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut intervals = intervals;
intervals.sort();
let mut res: Vec<Vec<i32>> = vec![intervals[0].clone()];
for interval in &intervals[1..] {
let last = res.last().unwrap().to_vec();
if interval[0] <= last[1] {
res.pop();
res.push(vec![last[0], max(last[1], interval[1])]);
} else {
res.push(interval.to_vec());
}
}
res
}
}
Merge 2 sorted arrays without extra space
❓: Given two sorted arrays arr1[] and arr2[] of sizes n and m in non-decreasing order. Merge them in sorted order. Modify arr1 so that it contains the first N elements and modify arr2 so that it contains the last M elements.
# Check another approach - Using gap method
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
1. Iterate throught both the arrays, if array2 element is less than array1 element,
then pop last item(zero) from arr1 and insert arr2 item into arr1 at that index
2. Make a count of number of zeros removed in that process
3. At the end of that iteration, there might be some large elements left over in arr2.
4. Insert them into arr1
"""
i = j = 0
zeroes_removed = 0
while i < m + n and j < n:
if nums1[i] > nums2[j]:
zeroes_removed += 1
nums1.pop()
nums1.insert(i, nums2[j])
j += 1
i += 1
for i in range(m + zeroes_removed, m + n):
nums1[i] = nums2[j]
j += 1
impl Solution {
pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
let mut i: usize = 0;
let mut j: usize = 0;
let um: usize = m as usize;
let un: usize = n as usize;
while i < um + un && j < un {
if nums2[j] < nums1[i] {
nums1.pop();
nums1.insert(i, nums2[j]);
j += 1;
}
i += 1;
}
for i in um + j..um + un {
nums1[i] = nums2[j];
j += 1;
}
}
}
Duplicate in array of n+1 integers
❓: Given an array of N + 1 size, where each element is between 1 and N. Assuming there is only one duplicate number, your task is to find the duplicate number.
🧠:
Floyd's Cycle Detection
1. Slow moves one point at a time
2. Fast moves 2 points at a time.
3. After they colloide, if we reset first pointer, and move that and slow pointer at a time, they will colloide at our result.
Please check here for formula and intuition
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow2 = 0
while True:
slow = nums[slow]
slow2 = nums[slow2]
if slow == slow2:
return slow
use std::collections::HashSet;
impl Solution {
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
let mut set: HashSet<i32> = HashSet::new();
for num in nums {
if set.contains(&num) {
return num;
}
set.insert(num);
}
return 1;
}
}
Repeating and Missing number
❓: You are given a read-only array of N integers with values also in the range [1, N] both inclusive. Each integer appears exactly once except A which appears twice and B which is missing. The task is to find the repeating and missing numbers A and B where A repeats twice and B is missing.
🧠:
Simple Maths Equations
1. Find sum of n numbers and find X - Y value. (X- Repeating, Y - Missing)
2. Find sum of squares of n numbers and form second equation. (X2 - Y2 = (X+Y)(X-Y)). From which we can get X + Y value
3. From those 2 equations, X and Y can be found out
Please check here for formula and intuition
class Solution:
def missingNumber(self, nums: list[int]) -> list[int, int]:
n = len(nums)
Sn = n * (n + 1) // 2
S2n = n * (n + 1) * (2 * n + 1) / 6
my_Sn = my_S2n = 0
for num in nums:
my_Sn += num
my_S2n += num * num
# equation1 - X+Y = (my_S2n - S2n) / (my_Sn-Sn)
equation_1_value = (my_S2n - S2n) / (my_Sn - Sn)
# equation2 - X-Y = my_Sn- Sn
equation_2_value = my_Sn - Sn
return [
(equation_1_value + equation_2_value) // 2,
(equation_1_value - equation_2_value) // 2,
]
obj = Solution()
assert obj.missingNumber([3, 1, 2, 5, 3]) == [3, 4]
assert obj.missingNumber([3, 1, 2, 5, 4, 6, 7, 5]) == [5, 8]
fn find_duplicate(nums: Vec<i32>) -> (i32, i32) {
let n: i32 = nums.len() as i32;
let sn: i32 = n * (n + 1) / 2;
let s2n: i32 = n * (n + 1) * (2 * n + 1) / 6;
let mut c_sn = 0;
let mut c_s2n = 0;
for num in nums {
c_sn += num;
c_s2n += num * num;
}
let eq1 = (c_s2n - s2n) / (c_sn - sn);
let eq2 = c_sn - sn;
((eq1 + eq2) / 2, (eq1 - eq2) / 2)
}
fn main() {
assert_eq!((3, 4), find_duplicate(vec![3, 1, 2, 5, 3]));
assert_eq!((5, 8), find_duplicate(vec![3, 1, 2, 5, 4, 6, 7, 5]));
}
Inversion of Array
Coming Soon