Part3
Search in 2d Matrix
❓: Search in a sorted 2D matrix
Approach 1:
Simple Maths Equations
1. Iterate through each row and check whether target can exist in that row or not
2. If yes, do a binary search
3. From those 2 equations, X and Y can be found out
Time Complexity -> O(n + logm)
class Solution:
def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
for row in matrix:
if row[0] <= target <= row[-1]:
return self.binary_search(row, target)
return False
def binary_search(self, row, target) -> bool:
n = len(row)
low, high = 0, n - 1
while low <= high:
mid = (low + high) // 2
if row[mid] == target:
return True
elif row[mid] < target:
low = mid + 1
else:
high = mid - 1
return False
"""
Approach2 ->
Do binary search on entire matrix, Trick Formula -> from mid integer, row and column are mid//m and mid%m.
Time Complexity -> O(logn + logm)
"""
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
n, m = len(matrix), len(matrix[0])
low, high = 0, m * n - 1
while low <= high:
mid = (low + high) // 2
r, c = mid // m, mid % m
if matrix[r][c] == target:
return True
elif matrix[r][c] < target:
low = mid + 1
else:
high = mid - 1
return False
impl Solution {
pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
let n = matrix.len();
let m = matrix[0].len();
let (mut low, mut high) = (0, n * m - 1);
while low <= high {
let mid = (low + high) / 2;
let (r, c) = (mid / m, mid % m);
if matrix[r][c] == target {
return true;
} else if matrix[r][c] < target {
low = mid + 1;
} else {
if mid == 0 {
break;
}
high = mid - 1;
}
}
false
}
}
func searchMatrix(matrix [][]int, target int) bool {
n, m := len(matrix), len(matrix[0])
low, high := 0, n*m-1
var mid, r, c int
for low <= high {
mid = (low + high) / 2
r, c = mid/m, mid%m
if matrix[r][c] == target {
return true
} else if matrix[r][c] < target {
low = mid + 1
} else {
high = mid - 1
}
}
return false
}
Pow(x,n)
❓: Given a double x and integer n, calculate x raised to power n. Basically Implement pow(x, n).
🧠
6 ** 5
ans = 6
6 ** 4
(6 * 6) ** 2
36 ** 2
(36**36) ** 1
ans = ans * 36*36
1. If power if odd, multiply the curr number to ans and reduce curr number by 1
2. If power if even, square the curr number and reduce the power by half
TC - O(logn)
SC - O(1)
class Solution:
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1.0
res = 1.0
dummy_n = abs(n)
while dummy_n > 1:
if dummy_n % 2:
res *= x
dummy_n -= 1
else:
x *= x
dummy_n //= 2
res *= x
if n < 0:
res = 1 / res
return res
impl Solution {
pub fn my_pow(x: f64, n: i32) -> f64 {
if n == 0 {
return 1.0;
}
let mut x = x;
let ox = x.clone(); //original x
let mut dn = if n == i32::MIN { i32::MAX } else { n.abs() }; //duplicate n
let mut res = 1.0;
while dn > 1 {
if dn % 2 == 1 {
res *= x;
dn -= 1;
} else {
x *= x;
dn /= 2;
}
}
res *= x;
if n == i32::MIN {
res *= ox;
}
if n < 0 {
res = 1.0 / res;
}
res
}
}
func myPow(x float64, n int) float64 {
if n == 0 {
return 1
}
res := 1.0
dummy_n := func(n int) int {
if n < 0 {
return -n
}
return n
}(n)
for dummy_n > 1 {
if dummy_n%2 == 1 {
res *= x
dummy_n -= 1
} else {
x *= x
dummy_n /= 2
}
}
res *= x
if n < 0 {
res = 1 / res
}
return res
}
Majority Element (>n/2 times)
❓: Given an array of N integers, write a program to return an element that occurs more than N/2 times in the given array. You may consider that such an element always exists in the array.
# Cancelling out if count if zero. If it is majority element, count won't become zero (won't be cancelled out)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
curr = nums[0]
count = 1
for num in nums[1:]:
if count == 0:
curr = num
count = 1
elif num == curr:
count += 1
else:
count -= 1
return curr
impl Solution {
pub fn majority_element(nums: Vec<i32>) -> i32 {
let mut res = nums[0];
let mut count = 1;
for &num in &nums[1..] {
if num == res {
count += 1
} else {
count -= 1;
if count == 0 {
res = num;
count = 1;
}
}
}
res
}
}
func majorityElement(nums []int) int {
res, count := nums[0], 1
for _, num := range nums[1:] {
if count == 0 {
res = num
count = 1
} else if num == res {
count += 1
} else {
count -= 1
}
}
return res
}
Majority Element (>n/3 times)
❓: Given an array of N integers. Find the elements that appear more than N/3 times in the array. If no such element exists, return an empty vector.
🧠:
Same as previous majority element algo. The difference is we apply the same algo for 2 elements and at the end we will find out which occurs more than n/3 times manually again.
Time - O(2n)
Space - O(1)
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
e1 = e2 = None
c1 = c2 = 0
for num in nums:
if c1 == 0 and e2 != num:
e1 = num
c1 = 1
elif c2 == 0 and e1 != num:
e2 = num
c2 = 1
elif num == e1:
c1 += 1
elif num == e2:
c2 += 1
else:
c1 -= 1
c2 -= 1
c1 = c2 = 0
for num in nums:
if num == e1:
c1 += 1
elif num == e2:
c2 += 1
n = len(nums)
res = []
if e1 is not None and c1 > n // 3:
res.append(e1)
if e2 is not None and c2 > n // 3:
res.append(e2)
return res
impl Solution {
pub fn majority_element(nums: Vec<i32>) -> Vec<i32> {
let (mut e1, mut e2, mut c1, mut c2) = (0, 1, 0, 0);
for &num in &nums {
if num == e1 {
c1 += 1
} else if num == e2 {
c2 += 1
} else if c1 == 0 {
e1 = num;
c1 = 1;
} else if c2 == 0 {
e2 = num;
c2 = 1;
} else {
c1 -= 1;
c2 -= 1;
}
}
let n = nums.len();
let (mut c1, mut c2) = (0, 0);
for &num in &nums {
if num == e1 {
c1 += 1;
}
if num == e2 {
c2 += 1;
}
}
let mut res: Vec<i32> = vec![];
if c1 > n / 3 {
res.push(e1)
}
if c2 > n / 3 {
res.push(e2)
}
res
}
}
func majorityElement(nums []int) []int {
e1, e2, c1, c2 := 0, 1, 0, 0
for _, num := range nums {
if c1 == 0 && e2 != num {
e1 = num
c1 = 1
} else if c2 == 0 && e1 != num {
e2 = num
c2 = 1
} else if num == e1 {
c1 += 1
} else if num == e2 {
c2 += 1
} else {
c1 -= 1
c2 -= 1
}
}
c1, c2 = 0, 0
for _, num := range nums {
if num == e1 {
c1 += 1
} else if num == e2 {
c2 += 1
}
}
n := len(nums)
res := []int{}
if c1 > n/3 {
res = append(res, e1)
}
if c2 > n/3 {
res = append(res, e2)
}
return res
}
Grid Unique Paths
❓: Given a matrix m X n, count paths from left-top to the right bottom of a matrix with the constraints that from each cell you can either only move to the rightward direction or the downward direction.
# Brute Force
# Time - m!*n!
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
"""
1. If curr indexes crossed the boundary, return 0
2. If curr indexes are at destination, return 1
3. Recursively perform the above by increasing the currrent indexes
"""
return self.helper(0, 0, m, n)
def helper(self, m1, n1, m, n):
if m1 >= m or n1 >= n:
return 0
if m1 == m - 1 and n1 == n - 1:
return 1
return self.helper(m1, n1 + 1, m, n) + self.helper(m1 + 1, n1, m, n)
# Optimal - DP Approach
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
"""
Idea is same as above, but the difference is, once you compute the value of a node, store it and use that value if that node is called again
"""
return self.helper(0, 0, m, n, {})
def helper(self, m1, n1, m, n, dp):
if (m1, n1) in dp:
return dp[(m1, n1)]
if m1 >= m or n1 >= n:
return 0
if m1 == m - 1 and n1 == n - 1:
return 1
dp[(m1, n1)] = self.helper(m1, n1 + 1, m, n, dp) + self.helper(
m1 + 1, n1, m, n, dp
)
return dp[(m1, n1)]
use std::collections::HashMap;
impl Solution {
pub fn unique_paths(m: i32, n: i32) -> i32 {
let mut dp: HashMap<(i32, i32), i32> = HashMap::new();
return Solution::helper(0, 0, m, n, &mut dp);
}
fn helper(r: i32, c: i32, m: i32, n: i32, dp: &mut HashMap<(i32, i32), i32>) -> i32 {
if dp.contains_key(&(r, c)) {
return dp[&(r, c)];
}
if r == m || c == n {
return 0;
}
if r == m - 1 && c == n - 1 {
return 1;
}
let left = Solution::helper(r, c + 1, m, n, dp);
let right = Solution::helper(r + 1, c, m, n, dp);
dp.insert((r, c), left + right);
return dp[&(r, c)];
}
}
func uniquePaths(m int, n int) int {
type Key struct {
r, c int
}
var helper func(r, c int) int
dp := map[Key]int{}
helper = func(r, c int) int {
if val, ok := dp[Key{r, c}]; ok {
return val
}
if r == m || c == n {
return 0
} else if r == m-1 && c == n-1 {
return 1
}
dp[Key{r, c}] = helper(r, c+1) + helper(r+1, c)
return dp[Key{r, c}]
}
return helper(0, 0)
}
Reverse Pairs
Coming Soon