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;
                }
            }
        }
    }
}

📘 💻

---

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
    }
}

📘 💻

---

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
    }
}

📘 💻

---

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
            }
        }
    }
}

📘 💻

---

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
    }
}

📘 💻