LeetCode Top 150 Flashcards
45. Jump Game II, solve with O(n) time and O(1) space
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4]
Output: 2
Constraints:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
It’s guaranteed that you can reach nums[n - 1].
Intuition :
At any position ( i ), the maximum range we can reach is ( i + nums[i] ).
Using a greedy strategy, we try to jump as far as possible within our current range before incrementing the jump count.
Track the maximum range we can reach in the current jump window. When we exhaust this range, it means we must take another jump.
Algorithm :
Initialize Variables:
jumps to count the number of jumps taken.
current_end to track the farthest index we can reach in the current jump.
farthest to track the farthest index we can potentially reach overall.
Iterate Through the Array:
For every index ( i ), update the farthest reachable index: ( \text{farthest} = \max(\text{farthest}, i + \text{nums}[i]) ).
If ( i ) reaches current_end, increment the jumps counter and update current_end to farthest.
Stop Early:
If the current_end is greater than or equal to ( n - 1 ), we’ve reached the last index, so return jumps.
This approach ensures we take the minimum number of jumps while efficiently scanning the array.
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < n - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
}
274. H-Index, solve with O(n) time and O(1) space
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
Example 1:
Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.
Example 2:
Input: citations = [1,3,1]
Output: 1
Constraints:
n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000
Intuition
The problem involves finding the H-Index, which is defined as the maximum value h such that the researcher has published at least h papers that have been cited at least h times each.
From the intuition behind the problem:
Sorting the citations array helps simplify the process of determining the H-Index.
By iterating through the sorted array, we can compare the number of citations to the number of papers that meet or exceed that threshold.
Approach
Sort the citations in ascending order.
For each index i in the sorted array:
The number of papers with citations greater than or equal to citations[i] is n - i, where n is the total number of papers.
If citations[i] is greater than or equal to n - i, then n - i is a valid candidate for the H-Index.
Return the maximum value that satisfies the above condition.
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
for(int i=0;i<citations.length;i++){
if(citations[i]>= (citations.length-i)){
return citations.length-i;
}
}
return 0;
}
}
380. Insert Delete GetRandom O(1)
Implement the RandomizedSet class:
RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.
Example 1:
Input
[“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
Constraints:
-231 <= val <= 231 - 1
At most 2 * 105 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.
class RandomizedSet {
private Map<Integer, Integer> map = new HashMap<>();
private List<Integer> list = new ArrayList<>();
public RandomizedSet() {
}
public boolean insert(int val) {
if (map.containsKey(val)) {
return false;
}
list.add(val);
map.put(val, list.size() - 1);
return true;
}
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
int index = map.get(val);
int currElement = list.get(index);
int last = list.get(list.size() - 1);
list.set(index, last);
list.set(list.size() - 1, currElement);
map.put(list.get(index), index);
list.remove(list.size() - 1);
map.remove(val);
return true;
}
public int getRandom() {
Random r = new Random();
return list.get(r.nextInt(list.size()));
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/What is the two pointer approach in arrays?
The two pointer approach involves using two indices to traverse an array, often from opposite ends, to solve problems efficiently.
True or False: The two pointer technique can only be applied to sorted arrays.
False
Fill in the blank: The two pointer technique is commonly used to solve problems such as __________ and __________.
finding pairs that sum to a target, removing duplicates
Which of the following scenarios can utilize the two pointer approach? (a) Reversing an array (b) Merging two sorted arrays (c) Finding the maximum element
Both (a) and (b) can utilize the two pointer approach.
What is the time complexity of the two pointer approach in most cases?
O(n)
238. Product of Array Except Self, solve with brute force appraoch.
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
- Brute Force
So, the first and formost, the simplest method that comes to mind is, I can loop through the complete array using a pointer, say j, for every index i, and multiply all the elements at index j except when i == j. This would ensure that I skip the element at index i from being multiplied.
The Time Complexity for this solution would be O(n2).
Below is the Java Code for this approach.
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int ans[] = new int[n];
for(int i = 0; i < n; i++) {
int pro = 1;
for(int j = 0; j < n; j++) {
if(i == j) continue;
pro *= nums[j];
}
ans[i] = pro;
}
return ans;
}
}
238. Product of Array Except Self, solve with O(n) time and O(n) space
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
- Finding Prefix Product and Suffix Product
Similar to finding Prefix Sum Array, here we would intend to find the Prefix Product Array and Suffix Product Array for our original array, i.e. pre[i] = pre[i - 1] * a[i - 1] (yes, we multiply with a[i - 1] and not with a[i] on purpose) and similarly suff[i] = suff[i + 1] * a[i + 1].
Now, at any index i our final answer ans[i] would be given by ans[i] = pre[i] * suff[i]. Why? Because the pre[i] * suff[i] contains product of every element before i and every element after i but not the element at index i (and that is the reson why we excluded a[i] in our prefix and suffix product).
The Time Complexity would be O(n), but we are now using Auxilary Space of O(n) (excluding the final answer array).
Below is the Java Code for this approach
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int pre[] = new int[n];
int suff[] = new int[n];
pre[0] = 1;
suff[n - 1] = 1;
for(int i = 1; i < n; i++) {
pre[i] = pre[i - 1] * nums[i - 1];
}
for(int i = n - 2; i >= 0; i--) {
suff[i] = suff[i + 1] * nums[i + 1];
}
int ans[] = new int[n];
for(int i = 0; i < n; i++) {
ans[i] = pre[i] * suff[i];
}
return ans;
}
}
238. Product of Array Except Self, solve with O(n) time and O(1) space
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
- Directly store the product of prefix and suffix into the final answer array
The logic is, we don’t actually need seperate array to store prefix product and suffix products, we can do all the approach discussed in method 3 directly onto our final answer array.
The Time Complexity would be O(n) but now, the Auxilary Space is O(1) (excluding the final answer array).
Below is the Java Code for the above algorithm.
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int ans[] = new int[n];
Arrays.fill(ans, 1);
int curr = 1;
for(int i = 0; i < n; i++) {
ans[i] *= curr;
curr *= nums[i];
}
curr = 1;
for(int i = n - 1; i >= 0; i--) {
ans[i] *= curr;
curr *= nums[i];
}
return ans;
}
}
t134. Gas Station, solve it in O(n) time and O(1) space
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.
Example 1:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.
Constraints:
n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
Problem Breakdown:
You have gas stations arranged in a circle.
Each station has a certain amount of gas (gas[i]).
It costs a specific amount of gas (cost[i]) to travel from station i to station i+1.
You need to determine if there exists a starting gas station from which you can complete the entire circuit in a clockwise direction.
Key Observations:
If the total gas available is less than the total cost required, the journey is impossible.
If sum(gas) < sum(cost), return -1 immediately.
If the total gas is sufficient, there must be one unique starting station.
Even if you can’t start at some station, the journey might still be possible by starting at a later station.
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int tankCapacity = 0;
int totalGas = 0;
int totalCost = 0;
int gasStationIndex = 0;
for (int i = 0; i < n; i++) {
totalGas += gas[i];
totalCost += cost[i];
}
if (totalCost > totalGas) return -1;
for (int i = 0; i < n; i++) {
tankCapacity += gas[i] - cost[i];
if (tankCapacity < 0) {
tankCapacity = 0;
gasStationIndex = i + 1;
}
}
return gasStationIndex;
}
}
totalGas and totalCost will track the total gas and total cost over the entire route.
tankCapacity tracks the current gas balance while iterating.
gasStationIndex stores the potential starting index.
first loop:
This loop calculates the total gas (totalGas) and total cost (totalCost).
If totalGas is less than totalCost, return -1 immediately because completing the circuit is impossible.
The second loop iterates through each station.
At each station i, calculate the net gain/loss of gas: tankCapacity += gas[i] - cost[i].
If capacity (current balance) drops below zero:
Reset the balance (total = 0).
Move to the next station (index = i + 1).
This means station i cannot be the starting point, so try station i+1.
Here’s a step-by-step breakdown of the solution:
Problem Breakdown:
You have gas stations arranged in a circle.
Each station has a certain amount of gas (gas[i]).
It costs a specific amount of gas (cost[i]) to travel from station i to station i+1.
You need to determine if there exists a starting gas station from which you can complete the entire circuit in a clockwise direction.
Key Observations:
If the total gas available is less than the total cost required, the journey is impossible.
If sum(gas) < sum(cost), return -1 immediately.
If the total gas is sufficient, there must be one unique starting station.
Even if you can’t start at some station, the journey might still be possible by starting at a later station.
Code Breakdown:
java
Copy code
public int canCompleteCircuit(int[] gas, int[] cost) {
int sGas = 0, sCost = 0, res = 0, total = 0;
sGas and sCost will track the total gas and total cost over the entire route.
total tracks the current gas balance while iterating.
res stores the potential starting index.
Step 1: Check if Completing the Circuit is Possible
java
Copy code
for (int i = 0; i < gas.length; i++) {
sGas += gas[i];
sCost += cost[i];
}
if (sGas < sCost) return -1;
This loop calculates the total gas (sGas) and total cost (sCost).
If sGas (total gas) is less than sCost (total cost), return -1 immediately because completing the circuit is impossible.
Step 2: Find the Starting Station
java
Copy code
for (int i = 0; i < gas.length; i++) {
total += gas[i] - cost[i];
if (total < 0) {
total = 0;
res = i + 1;
}
}
return res;
The second loop iterates through each station.
At each station i, calculate the net gain/loss of gas: total += gas[i] - cost[i].
If total (current balance) drops below zero:
Reset the balance (total = 0).
Move to the next station (res = i + 1).
This means station i cannot be the starting point, so try station i+1.
Why Does This Work?
If the total gas is sufficient, the only reason you fail at a certain station is that the gas you had up to that point wasn’t enough.
Resetting at i + 1 ensures that you only consider the segment that can possibly succeed.
135. Candy, solve in O(n) time and O(n) space
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Example 1:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
Constraints:
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
Candy Distribution Problem Solution Explained
Problem Summary
You need to distribute candies to children based on their ratings such that:
1. Each child gets at least one candy.
2. Children with a higher rating than their neighbors get more candies.
The goal is to calculate the minimum number of candies required to satisfy these conditions.
Solution Outline
The approach involves two passes through the ratings array:
1. Left to Right Pass – Ensures higher-rated children to the right receive more candies.
2. Right to Left Pass – Ensures higher-rated children to the left receive more candies.
By performing these two passes, we ensure that both conditions are met.
Code
```java
public class Solution {
public int candy(int[] ratings) {
int n = ratings.length; // Get the number of children
int[] candies = new int[n]; // Initialize an array to store the number of candies for each child
// First pass: Check ratings from left to right
for (int i = 1; i < n; i++) {
if (ratings[i - 1] < ratings[i] && candies[i - 1] >= candies[i]) {
candies[i] = candies[i - 1] + 1;
}
}
// Second pass: Check ratings from right to left
for (int i = n - 2; i >= 0; i--) {
if (ratings[i + 1] < ratings[i] && candies[i + 1] >= candies[i]) {
candies[i] = candies[i + 1] + 1;
}
}
int totalCandies = 0;
// Calculate the total number of candies needed
for (int i = 0; i < n; i++) {
totalCandies += candies[i] + 1;
}
return totalCandies;
} } ~~~
Step-by-Step Explanation
### 1. Initialization
```java
int n = ratings.length;
int[] candies = new int[n];
~~~
- n stores the number of children.
- candies array is initialized to keep track of the candies given to each child.
- First Pass (Left to Right)
```java
for (int i = 1; i < n; i++) {
if (ratings[i - 1] < ratings[i] && candies[i - 1] >= candies[i]) {
candies[i] = candies[i - 1] + 1;
}
}
~~~
- Traverse the array from left to right.
- If the current child’s rating is higher than the previous child (ratings[i - 1] < ratings[i]), and the current child has fewer or equal candies, increment their candy count by one more than the previous child.
- Second Pass (Right to Left)
```java
for (int i = n - 2; i >= 0; i–) {
if (ratings[i + 1] < ratings[i] && candies[i + 1] >= candies[i]) {
candies[i] = candies[i + 1] + 1;
}
}
~~~
- Traverse the array from right to left.
- If the current child’s rating is higher than the next child (ratings[i + 1] < ratings[i]), and the current child has fewer or equal candies, increment their candy count by one more than the next child.
- Calculate Total Candies
```java
int totalCandies = 0;
for (int i = 0; i < n; i++) {
totalCandies += candies[i] + 1;
}
~~~
- Each child must have at least one candy, socandies[i] + 1ensures that every child receives the minimum required candies.
- Sum the candies to get the total number required.
Example Walkthrough
### Example 1
~~~
ratings = [1, 0, 2]
~~~
- Left to Right Pass:
- Start with [0, 0, 0]
- After pass: [1, 0, 1]
- Right to Left Pass:
- After pass: [2, 1, 2]
- Total Candies: 2 + 1 + 2 = 5
Example 2
~~~
ratings = [1, 2, 2]
~~~
- Left to Right Pass:
- Start with [0, 0, 0]
- After pass: [0, 1, 0]
- Right to Left Pass:
- No changes: [0, 1, 0]
- Total Candies: 1 + 2 + 1 = 4
Complexity Analysis
- Time Complexity: O(n) – Two linear passes through the ratings array.
- Space Complexity: O(n) – Additional array of size n for candies.
Key Points
- The solution guarantees that both conditions are satisfied by performing two passes.
- It ensures the minimum number of candies by distributing incrementally based on neighbors’ ratings.
42. Trapping Rain Water, solve in O(n) time and O(n) space
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
Let me explain this solution for the rain water trapping problem with a detailed breakdown of how it works.
First, let’s understand the core concept. The amount of water that can be trapped at any position depends on the minimum of the highest bars to its left and right, minus the height of the current position. This insight forms the foundation of our solution.
Let’s break down the solution step by step:
Understanding the Approach
The solution uses a concept called “boundaries” - for each position, we need to know:
1. The maximum height to its left
2. The maximum height to its right
This allows us to calculate how much water can be trapped at each position.
Implementation Details
Step 1: Creating Helper Arrays
```java
int[] left = new int[n];
int[] right = new int[n];
~~~
We create two arrays to store:
- left: Maximum height encountered from the left up to each position
- right: Maximum height encountered from the right up to each position
Step 2: Filling Left Max Heights
```java
left[0] = height[0];
for (int i = 1; i < n; i++) {
left[i] = Math.max(left[i - 1], height[i]);
}
~~~
For each position, we compare:
- The maximum height we’ve seen so far (left[i-1])
- The current height (height[i])
and store the larger value. This builds a running maximum from left to right.
Step 3: Filling Right Max Heights
```java
right[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i–) {
right[i] = Math.max(right[i + 1], height[i]);
}
~~~
Similar to Step 2, but working from right to left. For each position, we track the maximum height seen so far from the right side.
Step 4: Calculating Trapped Water
```java
int trappedWater = 0;
for (int i = 0; i < n; i++) {
int minHeight = Math.min(left[i], right[i]);
trappedWater += minHeight - height[i];
}
~~~
For each position:
1. Find the minimum of left and right boundaries (this determines how high water can rise)
2. Subtract the current height (this gives us the depth of water at this position)
3. Add this amount to our total
Example Walkthrough
Let’s take the first example: [0,1,0,2,1,0,1,3,2,1,2,1]
Consider position 2 (where height[2] = 0):
- Left maximum up to this point: max(0,1) = 1
- Right maximum after this point: max(2,1,0,1,3,2,1,2,1) = 3
- Minimum of these boundaries: min(1,3) = 1
- Water trapped = 1 - 0 = 1 unit
This same process repeats for each position, accumulating the total trapped water.
Time and Space Complexity
- Time Complexity: O(n) - we make three passes through the array
- Space Complexity: O(n) - we use two additional arrays of size n
This solution provides an efficient way to solve the problem by preprocessing the maximum heights from both directions, making it easier to calculate the trapped water at each position.
Would you like me to clarify any part of this explanation or walk through another example?
