Problem 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 the histogram. Examples Example 1: 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. ...
Problem There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step: Copy All: You can copy all the characters present on the screen (a partial copy is not allowed). Paste: You can paste the characters which are copied last time. Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen. ...
Minimum Depth of Binary Tree Problem Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Examples Example 1: graph TD; 3 --- 9 & 20; 20 --- 15 & 7; ...
Maximum Depth of Binary Tree Problem Given a binary tree, find its maximum depth. Definition A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. The number of nodes along the longest path from the root node down to the farthest leaf node. Depth of root node is 0. Example Example 1 ...
Refer the problem statement: Maximum Subarray Sum Let us try to understand how Kadane’s Algorithm work. This solution is similar to sliding window in a way. Pseudocode For at-least 1 non-negative numbers Here’s the pseudocode for Kadane’s algorithm based on your template, designed to handle arrays with non-negative sums: # Start maxGlobal <- 0 maxCurrent <- 0 # Loop over array for i from 0 to n-1 do maxCurrent <- maxCurrent + a[i] # If maxCurrent drops below 0, reset it to 0 if maxCurrent < 0 then maxCurrent <- 0 end if # Update maxGlobal if we've found a new maximum if maxGlobal < maxCurrent then maxGlobal <- maxCurrent end if end for ...
Problem Find the minimum element in the rotated sorted array. For example, the array a = [0, 1, 2, 4, 6, 8, 10] might become: [8, 10, 0, 1, 2, 4, 6] if it was rotated 2 times. [4, 6, 8, 10, 0, 1, 2] if it was rotated 4 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. ...
Problem You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin. ...
Problem Follow up for “Find Minimum in Rotated Sorted Array”: What if duplicates are allowed? Would this affect the run-time complexity? How and why? This is follow up of - Find Minimum in Rotated Sorted Array 1 - No duplicates allowed Examples Example 1: Input: nums = [1,3,5] Output: 1 ...
Problem You are given an array prices where prices[i] is the price of a given stock on the 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. OR ...
Problem Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) aka constant time complexity for each function. ...