Part1
Set Matrix Zeroes
❓: Given a matrix if an element in the matrix is 0 then you will have to set its entire column and row to 0 and then return the matrix.
🧠:
1. First find the indexes of rows and columns where 0 is present
2. Iterate through matrix again to make relevant items to zero
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
r: set[int] = set()
c: set[int] = set()
m, n = len(matrix), len(matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
r.add(i)
c.add(j)
for i in range(m):
for j in range(n):
if (i in r) or (j in c):
matrix[i][j] = 0
use std::collections::HashSet;
impl Solution {
pub fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
let mut r: HashSet<usize> = HashSet::new();
let mut c: HashSet<usize> = HashSet::new();
let n = matrix.len();
let m = matrix[0].len();
for i in 0..n {
for j in 0..m {
if matrix[i][j] == 0 {
r.insert(i);
c.insert(j);
}
}
}
for i in 0..n {
for j in 0..m {
if r.contains(&i) || c.contains(&j) {
matrix[i][j] = 0;
}
}
}
}
}
func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
r, c := map[int]bool{}, map[int]bool{}
for i := range m {
for j := range n {
if matrix[i][j] == 0 {
r[i] = true
c[j] = true
}
}
}
for i := range m {
for j := range n {
if r[i] == true || c[j] == true {
matrix[i][j] = 0
}
}
}
}
Next Permutation
Coming Soon
Pascals Triangle
❓: In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown in the figure below:
Given the number of rows n. Print the first n rows of Pascal’s triangle..
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
result = [[1]]
if numRows == 1:
return result
for _ in range(2, numRows + 1):
result.append(self.next_pascal_row(result[-1]))
return result
def next_pascal_row(self, row: list[int]):
result = [1]
for i in range(1, len(row)):
result.append(row[i] + row[i - 1])
result.append(1)
return result
impl Solution {
pub fn generate(n: i32) -> Vec<Vec<i32>> {
let mut res: Vec<Vec<i32>> = vec![vec![1]];
if n == 1 {
return res;
}
for i in 2..=n {
let last = res.last().unwrap();
res.push(Solution::next_row(last));
}
res
}
pub fn next_row(last: &Vec<i32>) -> Vec<i32> {
let mut res: Vec<i32> = vec![1];
for i in 1..last.len() {
res.push(last[i] + last[i - 1]);
}
res.push(1);
res
}
}
func generate(numRows int) [][]int {
res := [][]int{{1}}
if numRows == 1 {
return res
}
for i := 2; i < numRows+1; i++ {
res = append(res, next_row(res[len(res)-1]))
}
return res
}
func next_row(prev_row []int) []int {
res := []int{1}
for i := 1; i < len(prev_row); i++ {
res = append(res, prev_row[i]+prev_row[i-1])
}
res = append(res, 1)
return res
}
Kadanes Algorithm
❓: Given an integer array arr, find the contiguous subarray (containing at least one number) which
has the largest sum and returns its sum
# TODO Print actual sub array as follow up question
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
maxi_sum = nums[0]
curr_sum = nums[0]
for item in nums[1:]:
curr_sum = max(item, curr_sum + item)
maxi_sum = max(maxi_sum, curr_sum)
return maxi_sum
use std::cmp::max;
impl Solution {
pub fn max_sub_array(nums: Vec<i32>) -> i32 {
let mut res = nums[0];
let mut curr = nums[0];
for num in &nums[1..] {
if curr < 0 {
curr = 0;
}
curr += num;
res = max(res, curr);
}
res
}
}
func maxSubArray(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
curr_sum, maxi_sum := nums[0], nums[0]
for i := 1; i < n; i++ {
curr_sum = max(nums[i], curr_sum+nums[i])
maxi_sum = max(maxi_sum, curr_sum)
}
return maxi_sum
}
Sort list Of 0s,1s,2s
❓: Given an array consisting of only 0s, 1s, and 2s. Write a program to in-place sort the array without using inbuilt sort functions. ( Expected: Single pass-O(N) and constant space)
class Solution:
def sortColors(self, nums: List[int]) -> None:
li = 0
ri = len(nums) - 1
curr = li
while curr <= ri:
if nums[curr] == 0:
nums[curr], nums[li] = nums[li], nums[curr]
li += 1
curr += 1
elif nums[curr] == 2:
nums[curr], nums[ri] = nums[ri], nums[curr]
ri -= 1
elif nums[curr] == 1:
curr += 1
impl Solution {
pub fn sort_colors(nums: &mut Vec<i32>) {
let n = nums.len();
let mut l: usize = 0;
let mut r: usize = n - 1;
let mut curr: usize = 0;
while curr <= r {
if nums[curr] == 0 {
nums.swap(l, curr);
l += 1;
curr += 1;
} else if nums[curr] == 2 {
nums.swap(r, curr);
if r == 0 {
break;
}
r -= 1;
} else {
curr += 1
}
}
}
}
func sortColors(nums []int) {
l, r, c := 0, len(nums)-1, 0
for c <= r {
if nums[c] == 0 {
nums[c], nums[l] = nums[l], nums[c]
l += 1
c += 1
} else if nums[c] == 1 {
c += 1
} else {
nums[c], nums[r] = nums[r], nums[c]
r -= 1
}
}
}
Stock Buy and Sell
❓: You are given an array of prices where prices[i] is the price of a given stock on an ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 1:
return 0
result = 0
curr_mini = prices[0]
for item in prices[1:]:
curr_mini = min(curr_mini, item)
result = max(result, item - curr_mini)
return result
use std::cmp::{max, min};
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let mut mini: i32 = i32::MAX;
let mut res: i32 = 0;
for price in prices {
mini = min(mini, price);
res = max(res, price - mini);
}
res
}
}
func maxProfit(prices []int) int {
n := len(prices)
if n == 1 {
return 0
}
mini := prices[0]
res := 0
for i := 1; i < n; i++ {
mini = min(mini, prices[i])
res = max(res, prices[i]-mini)
}
return res
}