Part2
Next Smaller Element
🧠:
1. Use stack. Iterate through items and remove items from stack whose value is greater than or equal to current num.
2. Next smaller element is element present in top of stack. If stack is empty, there is not next smaller element.
def nextSmallerElement(A, n):
stack = []
res = []
for a in A[::-1]:
while stack and stack[-1] >= a:
stack.pop()
res.append(stack[-1] if stack else -1)
stack.append(a)
return res[::-1]
fn nse(nums: Vec<i32>) -> Vec<i32> {
let mut stack: Vec<i32> = vec![];
let mut res: Vec<i32> = vec![];
for num in nums.iter().rev() {
while !stack.is_empty() && stack.last().unwrap() >= num {
stack.pop();
}
res.push(*stack.last().unwrap_or(&-1));
stack.push(*num);
}
res.reverse();
res
}
fn main() {
assert_eq!(nse(vec![4, 5, 2, 10, 8]), vec![2, 2, -1, 8, -1]);
assert_eq!(nse(vec![3, 2, 1]), vec![2, 1, -1]);
assert_eq!(nse(vec![1, 2, 3]), vec![-1, -1, -1]);
}
Largest rectangle in a histogram
❓: Given an array of integers heights representing the histogram's bar height where the width of each bar is 1 return the area of the largest rectangle in histogram.
Example:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
🧠:
For every height, possible rectangle width is nse-pse-1
class Solution:
def largestRectangleArea(self, heights: list[int]) -> int:
nse_arr = self.nse(heights)
pse_arr = self.pse(heights)
res = 0
for i in range(len(heights)):
res = max(res, heights[i] * (nse_arr[i] - pse_arr[i] - 1))
return res
def nse(self, heights):
res = []
stack = []
for ind in range(len(heights) - 1, -1, -1):
height = heights[ind]
while stack and heights[stack[-1]] >= height:
stack.pop()
res.append(stack[-1] if stack else len(heights))
stack.append(ind)
return res[::-1]
def pse(self, heights):
res = []
stack = []
for ind, height in enumerate(heights):
while stack and heights[stack[-1]] >= height:
stack.pop()
res.append(stack[-1] if stack else -1)
stack.append(ind)
return res
use std::cmp::max;
impl Solution {
pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
let nse_vec: Vec<i32> = Solution::nse(&heights);
let pse_vec: Vec<i32> = Solution::pse(&heights);
let mut res: i32 = 0;
for i in 0..heights.len() {
res = max(res, heights[i] * (nse_vec[i] - pse_vec[i] - 1))
}
res
}
pub fn nse(heights: &Vec<i32>) -> Vec<i32> {
let mut res: Vec<i32> = vec![];
let mut stack: Vec<i32> = vec![];
let n: i32 = heights.len() as i32;
for ind in (0..heights.len()).rev() {
while !stack.is_empty() && heights[*stack.last().unwrap() as usize] >= heights[ind] {
stack.pop();
}
res.push(*stack.last().unwrap_or(&n));
stack.push(ind as i32);
}
res.reverse();
res
}
pub fn pse(heights: &Vec<i32>) -> Vec<i32> {
let mut res: Vec<i32> = vec![];
let mut stack: Vec<i32> = vec![];
for ind in 0..heights.len() {
while !stack.is_empty() && heights[*stack.last().unwrap() as usize] >= heights[ind] {
stack.pop();
}
res.push(*stack.last().unwrap_or(&-1));
stack.push(ind as i32);
}
res
}
}
Sliding Window Maximum
❓: Given an array of integers arr, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Example:
Input: arr = [4,0,-1,3,5,3,6,8], k = 3
Output: [4,3,5,5,6,8]
Explanation:
Window position Max
------------------------ -----
[4 0 -1] 3 5 3 6 8 - 4
4 [0 -1 3] 5 3 6 8 - 3
4 0 [-1 3 5] 3 6 8 - 5
4 0 -1 [3 5 3] 6 8 - 5
4 0 -1 3 [5 3 6] 8 - 6
4 0 -1 3 5 [3 6 8] - 8
For each window of size k=3, we find the maximum element in the window and add it to our output array.
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
deque = []
n = len(nums)
res = []
for ind, num in enumerate(nums):
if deque and deque[0] <= ind - k:
deque.pop(0)
while deque and nums[deque[-1]] < num:
deque.pop()
deque.append(ind)
if ind >= k - 1:
res.append(nums[deque[0]])
return res
impl Solution {
pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
let mut deque: Vec<usize> = Vec::new();
let mut res: Vec<i32> = Vec::new();
for (ind, num) in nums.iter().enumerate() {
if !deque.is_empty() && deque[0] as i32 <= ind as i32 - k {
deque.remove(0);
}
while !deque.is_empty() && nums[*deque.last().unwrap()] <= *num {
deque.pop();
}
deque.push(ind);
if ind >= (k - 1) as usize {
res.push(nums[deque[0]]);
}
}
res
}
}
Implement Min Stack
❓: Implement Min Stack | O(2N) and O(N) Space Complexity. Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Example:
Input Format:["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"]
[
[ ], [-2], [0], [-3], [ ], [ ], [ ], [ ]
]
Result: [null, null, null, null, -3, null, 0, -2]
class MinStack:
def __init__(self):
self.stack = []
self.mini_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if self.mini_stack:
self.mini_stack.append(min(self.mini_stack[-1], val))
else:
self.mini_stack.append(val)
def pop(self) -> None:
self.stack.pop()
self.mini_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.mini_stack[-1]
use std::cmp::min;
struct MinStack {
stack: Vec<i32>,
min_stack: Vec<i32>,
}
impl MinStack {
fn new() -> Self {
MinStack {
stack: Vec::new(),
min_stack: Vec::new(),
}
}
fn push(&mut self, val: i32) {
if self.stack.is_empty() {
self.min_stack.push(val);
} else {
let top = self.min_stack.last().unwrap();
self.min_stack.push(min(*top, val));
}
self.stack.push(val);
}
fn pop(&mut self) {
self.stack.pop();
self.min_stack.pop();
}
fn top(&self) -> i32 {
*self.stack.last().unwrap()
}
fn get_min(&self) -> i32 {
*self.min_stack.last().unwrap()
}
}
Rotten Orange (Using BFS)
❓: You will be given an m x n grid, where each cell has the following values :
2 - represents a rotten orange 1 - represents a Fresh orange 0 - represents an Empty Cell Every minute, if a Fresh Orange is adjacent to a Rotten Orange in 4-direction ( upward, downwards, right, and left ) it becomes Rotten.
Return the minimum number of minutes required such that none of the cells has a Fresh Orange. If it's not possible, return -1.
Example:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4
🧠:
Use BFS
class Solution:
def orangesRotting(self, grid: list[list[int]]) -> int:
n = len(grid)
m = len(grid[0])
queue = []
bad_oranges = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 2:
bad_oranges += 1
queue.append((i, j))
res = -1
while queue:
for _ in range(len(queue)):
curr_i, curr_j = queue.pop(0)
for i, j in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
if (
self.is_valid(curr_i + i, curr_j + j, n, m)
and grid[curr_i + i][curr_j + j] == 1
):
grid[curr_i + i][curr_j + j] = 2
queue.append((curr_i + i, curr_j + j))
res += 1
for item in grid:
if 1 in item:
return -1
if bad_oranges == 0:
return 0
return res
def is_valid(self, i, j, n, m):
return (0 <= i < n) and (0 <= j < m)
impl Solution {
pub fn oranges_rotting(grid: Vec<Vec<i32>>) -> i32 {
let mut grid = grid;
let mut queue: Vec<(i32, i32)> = Vec::new();
let mut rotten = 0;
let (n, m) = (grid.len() as i32, grid[0].len() as i32);
for i in 0..n {
for j in 0..m {
let i = i as usize;
let j = j as usize;
if grid[i][j] == 2 {
rotten += 1;
queue.push((i as i32, j as i32));
}
}
}
let mut res = -1;
while !queue.is_empty() {
for _ in 0..queue.len() {
let curr = queue.remove(0);
let x_iter: Vec<i32> = vec![1, 0, -1, 0];
let y_iter: Vec<i32> = vec![0, 1, 0, -1];
for i in 0..4 {
let new_i = curr.0 + x_iter[i];
let new_j = curr.1 + y_iter[i];
if 0 <= new_i
&& new_i < n
&& 0 <= new_j
&& new_j < m
&& grid[new_i as usize][new_j as usize] == 1
{
grid[new_i as usize][new_j as usize] = 2;
queue.push((new_i, new_j));
}
}
}
res += 1;
}
for i in 0..n {
for j in 0..m {
if grid[i as usize][j as usize] == 1 {
return -1;
}
}
}
if rotten == 0 {
return 0;
}
res
}
}
Stock span problem
❓: Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.
The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.
For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
Implement the StockSpanner class:
StockSpanner() Initializes the object of the class. int next(int price) Returns the span of the stock's price given that today's price is price.
Example:
Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]
🧠:
Find pge
class StockSpanner:
def __init__(self):
self.prices = []
self.pge = []
def next(self, price: int) -> int:
self.prices.append(price)
n = len(self.prices)
while self.pge and self.prices[self.pge[-1]] <= price:
self.pge.pop()
res = n
if self.pge:
res = n - self.pge[-1] - 1
self.pge.append(n - 1)
return res
struct StockSpanner {
stocks: Vec<i32>,
pge: Vec<i32>,
}
impl StockSpanner {
fn new() -> Self {
StockSpanner {
stocks: Vec::new(),
pge: Vec::new(),
}
}
fn next(&mut self, price: i32) -> i32 {
self.stocks.push(price);
let n = self.stocks.len() as i32;
while !self.pge.is_empty() && self.stocks[*self.pge.last().unwrap() as usize] <= price {
self.pge.pop();
}
let mut res = n;
if !self.pge.is_empty() {
res = n - *self.pge.last().unwrap() - 1;
}
self.pge.push(n - 1);
res
}
}
The Celebrity Problem
❓: A celebrity is a person who is known by everyone else at the party but does not know anyone in return. Given a square matrix M of size N x N where M[i][j] is 1 if person i knows person j, and 0 otherwise, determine if there is a celebrity at the party. Return the index of the celebrity or -1 if no such person exists.
Note that M[i][i] is always 0.
Example:
Input: M = [ [0, 1, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0], [0, 1, 1, 0] ]
Output: 1
Explanation: Person 1 does not know anyone and is known by persons 0, 2, and 3. Therefore, person 1 is the celebrity.
from collections import defaultdict
class Solution:
def celebrity(self, M):
i_know = defaultdict(int)
know_me = defaultdict(int)
n = len(M)
m = len(M[0])
for i in range(n):
for j in range(m):
if M[i][j]:
i_know[i] += 1
know_me[j] += 1
for i in range(n):
if i_know[i] == 0 and know_me[i] == n - 1:
return i
return -1
use std::collections::HashMap;
fn celebrity(matrix: &[[i32; 4]; 4]) -> i32 {
let mut i_know: HashMap<usize, usize> = HashMap::new();
let mut know_me: HashMap<usize, usize> = HashMap::new();
let (m, n) = (matrix.len(), matrix[0].len());
for i in 0..m {
for j in 0..n {
if matrix[i][j] == 1 {
i_know.entry(i).and_modify(|e| *e += 1).or_insert(1);
know_me.entry(j).and_modify(|e| *e += 1).or_insert(1);
}
}
}
for i in 0..n {
if !i_know.contains_key(&i) && know_me[&i] == n - 1 {
return i as i32;
}
}
-1
}
fn main() {
let matrix = [[0, 1, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0], [0, 1, 1, 0]];
assert_eq!(celebrity(&matrix), 1);
}