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?
13. Roman to Integer, solve in O(n) time and O(1) space
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Example 1:
Input: s = “III”
Output: 3
Explanation: III = 3.
Example 2:
Input: s = “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
1 <= s.length <= 15
s contains only the characters (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’).
It is guaranteed that s is a valid roman numeral in the range [1, 3999].
class Solution {
public int romanToInt(String s) {
int answer = 0;
int previous = 0;
int number = 0;
for (int i = s.length() - 1; i >= 0; i--) {
switch (s.charAt(i)) {
case 'M' -> number = 1000;
case 'D' -> number = 500;
case 'C' -> number = 100;
case 'L' -> number = 50;
case 'X' -> number = 10;
case 'V' -> number = 5;
case 'I' -> number = 1;
}
if (number < previous) {
answer -= number;
} else {
answer += number;
}
previous = number;
}
return answer;
}
}
Let me help you understand how this solution converts Roman numerals to integers by breaking it down step by step.
First, let’s understand the core insight: this solution processes the Roman numeral from right to left, which is particularly clever because it allows us to easily handle the subtraction cases (like IV or IX) by comparing each number with the previous one we processed.
Let’s walk through how it works using the example “MCMXCIV” (1994):
Step 1: Variable Setup
- answer: Stores our running total (final answer)
- number: Stores the current Roman numeral’s value
- prev: Stores the previous Roman numeral’s value
- We start from the rightmost character and work backwards
Step 2: Processing Right-to-Left
Let’s see how the values change as we process “MCMXCIV”:
Starting with “V”:
~~~
Character: ‘V’
number = 5
prev = 0 (initial value)
Since number > prev: answer += 5
answer = 5, prev = 5
~~~
Next character “I”:
~~~
Character: ‘I’
number = 1
prev = 5
Since number < prev: answer -= 1
answer = 4, prev = 1
~~~
Next character “C”:
~~~
Character: ‘C’
number = 100
prev = 1
Since number > prev: answer += 100
answer = 104, prev = 100
~~~
Next character “X”:
~~~
Character: ‘X’
number = 10
prev = 100
Since number < prev: answer -= 10
answer = 94, prev = 10
~~~
Next character “M”:
~~~
Character: ‘M’
number = 1000
prev = 10
Since number > prev: answer += 1000
answer = 1094, prev = 1000
~~~
Next character “C”:
~~~
Character: ‘C’
number = 100
prev = 1000
Since number < prev: answer -= 100
answer = 994, prev = 100
~~~
Final character “M”:
~~~
Character: ‘M’
number = 1000
prev = 100
Since number > prev: answer += 1000
Final answer = 1994
~~~
The key elements that make this solution work:
- Right-to-Left Processing: This approach simplifies the handling of subtraction cases. Instead of having to look ahead to see if we need to subtract, we can look at what we’ve already processed.
- Comparison Logic: If the current number is less than the previous number we saw, we subtract it (handling cases like IV). Otherwise, we add it. This elegantly handles both regular addition (like VI = 6) and subtraction cases (like IV = 4).
- Switch Statement: The switch statement provides a clean way to convert each Roman numeral character to its corresponding integer value. The modern arrow syntax (
->) makes the code particularly readable. - Single Pass: The algorithm only needs to traverse the string once, making it efficient with O(n) time complexity where n is the length of the input string.
This solution demonstrates how choosing the right perspective (right-to-left processing) can significantly simplify what might otherwise be a more complex problem requiring lookahead or multiple passes through the string.
Would you like me to elaborate on any particular aspect of the solution?
12. Integer to Roman, solve in O(1) time and O(1) space
Seven different symbols represent Roman numerals with the following values:
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:
If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.
Given an integer, convert it to a Roman numeral.
Example 1:
Input: num = 3749
Output: “MMMDCCXLIX”
Explanation:
3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC as 500 (D) + 100 (C) + 100 (C)
40 = XL as 10 (X) less of 50 (L)
9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places
Example 2:
Input: num = 58
Output: “LVIII”
Explanation:
50 = L
8 = VIII
Example 3:
Input: num = 1994
Output: “MCMXCIV”
Explanation:
1000 = M
900 = CM
90 = XC
4 = IV
Constraints:
1 <= num <= 3999
class Solution {
public String intToRoman(int num) {
String thousands[] = {"", "M", "MM", "MMM"};
String hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
String tens[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
String ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX", "X"};
return thousands[num / 1000] + hundreds[(num % 1000) / 100] + tens[(num % 100) / 10] + ones[num % 10];
}
}
Let me break down how this solution works step by step:
- Array Structure Setup
First, the solution creates four arrays that store pre-computed Roman numeral patterns:
```java
String M[] = {“”, “M”, “MM”, “MMM”} // Thousands place
String C[] = {“”, “C”, “CC”, “CCC”, “CD”, “D”, “DC”, “DCC”, “DCCC”, “CM”} // Hundreds place
String X[] = {“”, “X”, “XX”, “XXX”, “XL”, “L”, “LX”, “LXX”, “LXXX”, “XC”} // Tens place
String I[] = {“”, “I”, “II”, “III”, “IV”, “V”, “VI”, “VII”, “VIII”, “IX”} // Ones place
~~~
- Array Contents Explanation
Each array handles a specific decimal place:
- M array (thousands): Can only go up to 3000 (MMM) since constraint is num ≤ 3999
- C array (hundreds): Handles 100 to 900
- X array (tens): Handles 10 to 90
- I array (ones): Handles 1 to 9
- Number Splitting Logic
The solution splits the input number into its decimal places using division and modulo:
```java
M[num/1000] // Gets thousands digit
C[(num%1000)/100] // Gets hundreds digit
X[(num%100)/10] // Gets tens digit
I[num%10] // Gets ones digit
~~~
- Example Walkthrough
Let’s take num = 2743:
-
num/1000 = 2- Looks up M[2] → “MM”
-
(num%1000)/100 = 7- num%1000 = 743
- 743/100 = 7
- Looks up C[7] → “DCC”
-
(num%100)/10 = 4- num%100 = 43
- 43/10 = 4
- Looks up X[4] → “XL”
-
num%10 = 3- Looks up I[3] → “III”
- Concatenates: “MM” + “DCC” + “XL” + “III” = “MMDCCXLIII”
- Key Benefits
- No need for complex if-else conditions
- Pre-computed patterns handle all subtractive cases automatically
- O(1) time complexity since the number of operations is constant
- Clean and maintainable code structure
The solution is elegant because it transforms what could be a complex series of conditional statements into simple array lookups and basic arithmetic operations.
Ah, let’s understand why each array starts with an empty string “” as its first element (index 0).
The key is in how the arithmetic works. Let’s look at what happens when a particular place value is 0:
Take the number 1035 as an example:
- For thousands:
1035/1000 = 1- This correctly gets M[1] = “M”
- For hundreds:
(1035%1000)/100 = 0- 1035%1000 = 35 (remainder after removing 1000)
- 35/100 = 0
- This gets C[0] = “” (empty string)
- We want an empty string here because there are no hundreds!
- For tens:
(1035%100)/10 = 3- 35%100 = 35
- 35/10 = 3
- Gets X[3] = “XXX”
- For ones:
1035%10 = 5- Gets I[5] = “V”
Final result: “M” + “” + “XXX” + “V” = “MXXXV”
If we didn’t have the empty string at index 0, we’d need additional logic to handle cases where a place value is zero. By including the empty string, we can simply concatenate the results without worrying about zero values - they automatically contribute nothing to the final string.
This is a clever way to handle zero values implicitly through array indexing rather than explicit conditional checks!
58. Length of Last Word in O(n) time and O(1) space
Given a string s consisting of words and spaces, return the length of the last word in the string.
A word is a maximal
substring
consisting of non-space characters only.
Example 1:
Input: s = “Hello World”
Output: 5
Explanation: The last word is “World” with length 5.
Example 2:
Input: s = “ fly me to the moon “
Output: 4
Explanation: The last word is “moon” with length 4.
Example 3:
Input: s = “luffy is still joyboy”
Output: 6
Explanation: The last word is “joyboy” with length 6.
Constraints:
1 <= s.length <= 104
s consists of only English letters and spaces ‘ ‘.
There will be at least one word in s.
Let me walk you through how this solution works to find the length of the last word in a string.
First, let’s understand the core method being used:
```java
public int lengthOfLastWord(String s) {
String[] split = s.split(“ “);
return split[split.length - 1].length();
}
~~~
The solution works by leveraging Java’s String manipulation capabilities in a clever way. Let’s break it down step by step:
- The
split()method: When we calls.split(" "), Java breaks the input string into an array of substrings wherever it finds a space character. For example:- For “Hello World” →
["Hello", "World"] - For “ fly me to the moon “ →
["", "fly", "me", "to", "the", "moon"] - For “luffy is still joyboy” →
["luffy", "is", "still", "joyboy"]
- For “Hello World” →
- An important detail about
split()is that it handles multiple consecutive spaces automatically. The method effectively removes empty strings that would result from consecutive spaces, so we don’t need to worry about the extra spaces in examples like the second one. - Once we have our array of words, we access the last word using
split[split.length - 1]. The array’s length minus 1 gives us the index of the last element. For example:- If
split = ["Hello", "World"], thensplit.lengthis 2, sosplit[1]gives us “World” - If
split = ["luffy", "is", "still", "joyboy"], thensplit[3]gives us “joyboy”
- If
- Finally, we call
length()on the last word to get its character count. Thelength()method returns the number of characters in the string.
This solution is particularly elegant because it handles all the edge cases mentioned in the constraints:
- It works for strings of any length between 1 and 10^4
- It handles multiple spaces between words
- It works correctly as long as there’s at least one word in the string
- It processes strings containing only English letters and spaces
However, it’s worth noting that while this solution is concise and readable, it does create a new array containing all words in the string. For very large strings, a more memory-efficient solution might scan the string from right to left and count characters until reaching a space. But for the given constraints (maximum length of 10^4), this solution is perfectly acceptable and much more maintainable.
Let me help you understand the time complexity of this solution by breaking down each operation:
- First, let’s look at the
split()method. When Java’s String.split() runs, it needs to:- Scan through the entire input string once to identify where the spaces are
- Create new substring objects for each word
- Store these substrings in an array
- Next, we access the last element of the array with
split[split.length - 1]. This is a constant time O(1) operation since we’re directly accessing an array element by its index. - Finally, getting the length of the last word with
length()is also an O(1) operation in Java, as String objects maintain their length as a field that can be accessed instantly.
Therefore, the overall time complexity is O(n), where n is the length of the input string. The dominant factor is the split() operation, while the other operations are constant time.
To put this in perspective, if we doubled the length of our input string, the time taken by the algorithm would roughly double as well. This linear relationship between input size and processing time makes the solution quite efficient for the given constraints (string length ≤ 10^4).
It’s worth noting that while we could write a solution that doesn’t use split() and instead scans from right to left (which would still be O(n)), the difference in actual performance would be minimal for the given constraints. The current solution prioritizes code readability and maintainability while still maintaining linear time complexity.
14. Longest Common Prefix, solve in O(nlogn) time and O(1) space
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
Example 1:
Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”
Example 2:
Input: strs = [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.
Constraints:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.
class Solution {
public String longestCommonPrefix(String[] strs) {
Arrays.sort(strs);
String s1 = strs[0];
String s2 = strs[strs.length - 1];
int index = 0;
while (index < s1.length() && index < s2.length()) {
if (s1.charAt(index) == s2.charAt(index)) {
index++;
} else {
break;
}
}
return s1.substring(0, index);
}
}
Let me explain how this solution cleverly finds the longest common prefix among an array of strings. The key insight is that if we sort the strings alphabetically, we only need to compare the first and last strings to find the common prefix.
Let’s break it down step by step:
First, consider what happens when we sort strings alphabetically:
```java
Arrays.sort(strs);
~~~
When strings are sorted, all strings with the same prefix will be grouped together. The first string (alphabetically smallest) and last string (alphabetically largest) in the sorted array will have the maximum possible difference. If these two strings share a common prefix, all strings between them must share that same prefix.
For example, with input [“flower”, “flow”, “flight”]:
After sorting: [“flight”, “flow”, “flower”]
- First string (s1) = “flight”
- Last string (s2) = “flower”
The code then compares these strings character by character:
```java
String s1 = strs[0]; // first string
String s2 = strs[strs.length - 1]; // last string
int index = 0;
while (index < s1.length() && index < s2.length()) {
if (s1.charAt(index) == s2.charAt(index)) {
index++;
} else {
break;
}
}
~~~
Let’s see how the comparison works in our example:
- index 0: ‘f’ == ‘f’ ✓ (increment index)
- index 1: ‘l’ == ‘l’ ✓ (increment index)
- index 2: ‘i’ != ‘o’ ✗ (break loop)
Finally, we extract the common prefix:
```java
return s1.substring(0, index);
~~~
This returns “fl”, which is indeed the longest common prefix.
The brilliance of this solution lies in its efficiency:
1. We don’t need to compare every string with every other string
2. We don’t need to check all characters in all strings
3. By using the sorted property, we only need to compare two strings
4. The solution handles edge cases naturally:
- If there’s no common prefix, we’ll break at index 0
- If one string is a prefix of all others, we’ll stop at its length
- If the array has only one string, it becomes both first and last string
Time complexity is O(S⋅log n + M) where:
- S is the length of the strings
- n is the number of strings
- M is the length of the common prefix
The space complexity is O(1) as we only store two string references and an index.
Why sorting is needed on finding the longest common prefix in the array? This question is based on the solution which uses sorting to find the longest common prefix.
Input: strs = [“flower”,”flow”,”flight”]
Let me explain why sorting is crucial for this solution to work correctly. I’ll break this down with examples to show why comparing just the first and last strings after sorting is sufficient.
Consider how strings are sorted alphabetically. When we sort strings, they get arranged based on character-by-character comparison from left to right. This creates an important property: any common prefix must be present in all strings between the first and last strings in the sorted array.
Let’s look at a detailed example:
~~~
Original array: [“flower”, “flow”, “flight”]
After sorting: [“flight”, “flow”, “flower”]
~~~
When these strings are sorted:
1. “flight” comes first because ‘i’ comes before ‘o’ in the alphabet
2. “flow” comes second because ‘o’ comes before ‘w’
3. “flower” comes last because it matches “flow” up to ‘w’ but has additional characters
Now, let’s understand why comparing just the first and last strings works:
- If there is a common prefix, it MUST be present in both the first and last strings:
First: "flight" -> starts with "fl" Last: "flower" -> starts with "fl"
Any string that would come between them alphabetically (like “flow”) must also share this prefix. This is because to be sorted between these strings, it must start with the same characters that match in both the first and last strings. - If the first and last strings don’t share a prefix at some position, no other string in the array can have a longer common prefix:
"flight" -> third character is 'i' "flower" -> third character is 'o'
Since ‘i’ comes before ‘o’ in the alphabet, any string with a different third character would either:- If the character comes before ‘i’: sort before “flight”
- If the character comes after ‘o’: sort after “flower”
- If the character is between ‘i’ and ‘o’: still not match one of the ends
Let’s see what would happen WITHOUT sorting:
~~~
Original array: [“flower”, “flow”, “flight”]
~~~
If we just compared the first and last strings without sorting:
~~~
First: “flower”
Last: “flight”
~~~
We would incorrectly find a common prefix of “fl”, but we wouldn’t be guaranteed that “flow” (the middle string) shares this prefix. We got lucky in this case because all strings do share “fl”, but in general, this approach wouldn’t work.
Consider this counterexample:
~~~
Unsorted: [“apple”, “zebra”, “appetite”]
~~~
Comparing just first and last without sorting would compare “apple” and “appetite”, finding “app” as a common prefix. But “zebra” in the middle doesn’t share this prefix at all.
After sorting:
~~~
Sorted: [“appetite”, “apple”, “zebra”]
~~~
Now comparing first and last strings correctly shows there is no common prefix, as “appetite” and “zebra” share no common starting characters.
This is why sorting is essential: it guarantees that if a prefix is common to the first and last strings, it must be common to all strings in between, because that’s the only way they could have been sorted into those positions. Without sorting, we lose this guarantee and can’t rely on just checking the endpoints of our array.
151. Reverse Words in a String, solve in O(n) time and O(n) space
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example 1:
Input: s = “the sky is blue”
Output: “blue is sky the”
Example 2:
Input: s = “ hello world “
Output: “world hello”
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: s = “a good example”
Output: “example good a”
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Constraints:
1 <= s.length <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ‘ ‘.
There is at least one word in s.
class Solution {
public String reverseWords(String s) {
String[] arr = s.trim().split("\\s+");
int i = 0;
int j = arr.length - 1;
while (i < j) {
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
return String.join(" ", arr);
}
}
Let me explain this solution step by step, breaking down how it reverses the words in a string while handling various edge cases.
Let’s start with understanding what the solution needs to accomplish:
1. Remove extra spaces (leading, trailing, and between words)
2. Reverse the order of words
3. Join the words back together with single spaces
Here’s how the solution works:
First, let’s look at the input preprocessing:
```java
String[] arr = s.trim().split(“\s+”);
~~~
- trim() removes leading and trailing spaces from the string. For example, “ hello world “ becomes “hello world”
- split("\\s+") splits the string into an array of words:
- \\s+ is a regular expression pattern that matches one or more whitespace characters
- This effectively handles multiple spaces between words
- For “hello world”, we get ["hello", "world"]
Next, the core reversal logic:
```java
int i = 0;
int j = arr.length - 1;
while (i < j) {
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j–;
}
~~~
This is implementing a two-pointer technique to reverse the array:
- i starts from the beginning (index 0)
- j starts from the end (last index)
- We swap elements at positions i and j using a temporary variable
- We move the pointers towards the center (i increases, j decreases)
- The process continues until the pointers meet in the middle
For example, with input ["the", "sky", "is", "blue"]:
1. First swap: “the” ↔ “blue” → ["blue", "sky", "is", "the"]
2. Second swap: “sky” ↔ “is” → ["blue", "is", "sky", "the"]
Finally, we join the words:
```java
return String.join(“ “, arr);
~~~
- String.join() concatenates all elements in the array
- The first argument “ “ specifies that we want a single space between elements
- This creates our final output string with proper spacing
Time Complexity: O(n), where n is the length of the input string
Space Complexity: O(n) to store the array of words
Regarding the follow-up question about solving it in-place with O(1) extra space: This Java solution doesn’t solve it in-place because Java strings are immutable. For an in-place solution, you would need a language with mutable strings (like C++) and would need to manipulate the characters directly within the string.
6. Zigzag Conversion, solve in O(n2) time and O(numRows) space.
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = “PAYPALISHIRING”, numRows = 3
Output: “PAHNAPLSIIGYIR”
Example 2:
Input: s = “PAYPALISHIRING”, numRows = 4
Output: “PINALSIGYAHRPI”
Explanation:
P I N
A L S I G
Y A H R
P I
Example 3:
Input: s = “A”, numRows = 1
Output: “A”
Constraints:
1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ‘,’ and ‘.’.
1 <= numRows <= 1000
class Solution {
public String convert(String s, int numRows) {
String[] ans = new String[numRows];
for (int i = 0; i < numRows; i++) {
ans[i] = "";
}
int j = 0;
while (j < s.length()) {
for (int i = 0; i < numRows && j < s.length(); i++) {
ans[i] += s.charAt(j++);
}
for (int i = numRows - 2; i > 0 && j < s.length(); i--) {
ans[i] += s.charAt(j++);
}
}
String result = "";
for (int i = 0; i < numRows; i++) {
result += ans[i];
}
return result;
}
}
Let me explain how this zigzag conversion solution works step by step.
First, let’s understand what the zigzag pattern means. When we write characters in a zigzag with n rows, we move down vertically for n characters, then move up diagonally until we reach the top row, then repeat. This creates a wave-like pattern.
Here’s how the solution works:
- Initialize Storage
```java
String[] ans = new String[numRows];
for (int i = 0; i < numRows; i++) {
ans[i] = “”;
}
~~~
We create an array of strings, one for each row. Each string will store the characters that belong in that row. We initialize each string as empty.
- Main Processing Loop
The solution has two main parts that alternate:
Part A: Moving Down Vertically
```java
for (int i = 0; i < numRows && j < s.length(); i++) {
ans[i] += s.charAt(j++);
}
~~~
This part moves down vertically, adding one character to each row from top to bottom. For example, with “PAYPAL” and 3 rows:
~~~
P
A
Y
~~~
Part B: Moving Up Diagonally
```java
for (int i = numRows - 2; i > 0 && j < s.length(); i–) {
ans[i] += s.charAt(j++);
}
~~~
This part moves up diagonally, adding characters to the middle rows (excluding the top and bottom rows). Continuing our example:
~~~
P A
A P L
Y
~~~
- Combining Results
```java
String result = “”;
for (int i = 0; i < numRows; i++) {
result += ans[i];
}
~~~
Finally, we combine all rows into a single string by concatenating them from top to bottom.
Example Walkthrough
Let’s see how it processes “PAYPALISHIRING” with 3 rows:
- First vertical movement: “P”, “A”, “Y”
- Diagonal movement up: “P” in row 2
- Second vertical movement: “A”, “L”, “I”
- Diagonal movement up: “S” in row 2
- Third vertical movement: “H”, “I”, “R”
- Diagonal movement up: “I” in row 2
- Final vertical movement: “N”, “G”
This creates:
~~~
P A H N
A P L S I I G
Y I R
~~~
When we combine these rows, we get “PAHNAPLSIIGYIR”.
Special Cases
The solution elegantly handles special cases:
- When numRows = 1, only the vertical movement happens
- When the string is shorter than numRows, it still works correctly
- The zigzag pattern adjusts automatically for different numbers of rows
This solution is efficient with O(n) time complexity, where n is the length of the input string, as it processes each character exactly once.
21. Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.
I’ll help you solve this linked list merging problem. Let’s break it down step by step and create a solution that’s both efficient and easy to understand.
First, let’s create the basic structure for our linked list node, then implement the merging logic:
/**
* Definition for singly-linked list node
*/
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// Create a dummy node to serve as the head of our merged list
// This eliminates the need for special cases when inserting the first node
ListNode dummy = new ListNode(0);
ListNode current = dummy;
// Continue while both lists have nodes to compare
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
// If list1's value is smaller, add it to our merged list
current.next = list1;
list1 = list1.next;
} else {
// If list2's value is smaller, add it to our merged list
current.next = list2;
list2 = list2.next;
}
// Move our pointer forward in the merged list
current = current.next;
}
// If there are remaining nodes in list1, append them
if (list1 != null) {
current.next = list1;
}
// If there are remaining nodes in list2, append them
if (list2 != null) {
current.next = list2;
}
// Return the head of our merged list (skip the dummy node)
return dummy.next;
}
}
Let’s understand how this solution works:
- We start by creating a dummy node. This is a common technique in linked list problems because it simplifies our logic by eliminating the need to handle the first node as a special case.
- The merging process works like this:
- We maintain a
currentpointer that keeps track of where we’re building our merged list - We compare values from both lists and take the smaller one each time
- We move forward in the list we took the node from
- We update our
currentpointer to point to the newly added node
- We maintain a
- The while loop continues as long as we have nodes to compare in both lists. Once we run out of nodes in either list, we handle any remaining nodes.
- For remaining nodes, we can simply point our
current.nextto whichever list still has nodes. Since both input lists are already sorted, we know any remaining nodes are in the correct order.
Time Complexity: O(n + m) where n and m are the lengths of the input lists. We need to process every node exactly once.
Space Complexity: O(1) because we’re only rearranging pointers and not creating any new nodes (except the dummy node).
For example, let’s trace through merging [1,2,4] and [1,3,4]:
1. Compare 1 and 1: Take either, advance that list
2. Compare 2 and 1: Take 1, advance list2
3. Compare 2 and 3: Take 2, advance list1
4. Compare 4 and 3: Take 3, advance list2
5. Compare 4 and 4: Take either, advance that list
6. Take remaining node(s)
The result will be [1,1,2,3,4,4], exactly as required.
