Each row starts and ends with 1. For intermediate elements, the value equals the sum of the two elements above it from the previous row. We can build rows iteratively from top to bottom.
🔢 Java Code (Iterative)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
import java.util.*;
classSolution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> res = newArrayList<>(); for (inti=0; i < numRows; i++) { List<Integer> row = newArrayList<>(); for (intj=0; j <= i; j++) { if (j == 0 || j == i) row.add(1); else { List<Integer> prev = res.get(i - 1); row.add(prev.get(j - 1) + prev.get(j)); } } res.add(row); } return res; } }
⏱ Complexity Analysis
Time: O(numRows^2) — we fill each entry of the triangle once.
Space: O(numRows^2) — output size.
✍️ Summary
Build each row using the previous row’s values.
Simple, iterative approach works efficiently for the problem constraints.
A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
💬 Example
1 2 3 4 5
Input: S = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". Each letter appears in at most one part.
💡 Intuition
We want to cut the string into maximum number of parts such that no character appears in more than one part. Key idea: for each character, precompute its last occurrence index. Then scan the string and maintain a running end which is the farthest last occurrence of characters seen so far. When the current index reaches end, we can close a partition (from previous cut to end) and start a new one.
This is a greedy strategy: always close a partition as soon as every character inside it cannot appear later.
You are given a 0-indexed array of integers nums of length n. You are initially positioned at the first index. Each element nums[i] represents the maximum length of a forward jump from index i.
Return the minimum number of jumps to reach the last index. The test cases are generated such that you can always reach the last index.
💬 Examples
Example 1
1 2 3 4
Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2
1 2
Input: nums = [2,3,0,1,4] Output: 2
💡 Intuition
This problem can be solved using a greedy approach.
We want to minimize the number of jumps.
Track two variables while scanning:
currentEnd: the farthest point reachable with the current number of jumps.
farthest: the farthest point reachable by the next jump.
Each time we reach currentEnd, we must make another jump, and update currentEnd = farthest.
This guarantees minimum jumps since we always extend as far as possible at each step.
🔢 Java Code (Greedy)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution { publicintjump(int[] nums) { intjumps=0; intfarthest=0; intcurrentEnd=0; for (inti=0; i < nums.length - 1; i++) { farthest = Math.max(farthest, i + nums[i]); if (i == currentEnd) { jumps++; currentEnd = farthest; } } return jumps; } }
⏱ Complexity Analysis
Time: O(n) — linear scan.
Space: O(1).
✍️ Summary
Use a greedy strategy to expand the farthest reach at each step.
Each time you exhaust the current range, increment jumps and move to the next range.
You are given an integer array nums. You are initially positioned at the first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
💬 Examples
Example 1
1 2 3
Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2
1 2 3
Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 with a maximum jump length 0, so cannot move forward.
💡 Intuition
We need to check whether it’s possible to reach the last index:
Keep track of the farthest position reachable while traversing the array.
If at any index i, i > farthest, then we cannot reach this index → return false.
Otherwise, update farthest = max(farthest, i + nums[i]).
If the farthest index is at least the last index, return true.
This is a classic greedy approach.
🔢 Java Code (Greedy)
1 2 3 4 5 6 7 8 9 10
classSolution { publicbooleancanJump(int[] nums) { intfarthest=0; for (inti=0; i < nums.length; i++) { if (i > farthest) returnfalse; farthest = Math.max(farthest, i + nums[i]); } returntrue; } }
⏱ Complexity Analysis
Time: O(n) — single pass.
Space: O(1).
✍️ Summary
Maintain the farthest index reachable while iterating.
If you ever get stuck (i > farthest), return false.
You are given an array prices where prices[i] is the price of a given stock on the i-th 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.
💬 Examples
Example 1
1 2 3
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.
Example 2
1 2 3
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done and the max profit = 0.
💡 Intuition
We want the largest difference prices[j] - prices[i] with j > i. A simple linear scan can track the minimum price so far and compute the potential profit at each day by subtracting the current min from the current price. Keep the maximum profit encountered. This is a greedy O(n) solution.
You can view the problem as finding the maximum subarray sum of daily differences diff[i] = prices[i] - prices[i-1]. Apply Kadane’s algorithm to diff to get the same O(n) result.
⏱ Complexity Analysis
Time: O(n) — single pass through prices.
Space: O(1) — constant extra memory.
✍️ Summary
Track the minimum buying price so far and update the maximum profit at each step.
Very efficient greedy solution: O(n) time, O(1) space.
Given an integer array nums and an integer k, return the k-th largest element in the array. Note: It is the k-th largest element in the sorted order, not the k-th distinct element.
💬 Examples
Example 1
1 2
Input: nums = [3,2,1,5,6,4], k = 2 Output: 5
Example 2
1 2
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4
💡 Intuition
There are two common approaches:
Heap (Min-Heap of size k):
Maintain a heap of the largest k elements.
The root of the heap is the answer.
Time: O(n log k).
Quickselect (Hoare’s selection algorithm):
Similar to quicksort partitioning.
Average time: O(n), worst-case O(n²).
More efficient in practice.
🔢 Java Code (Heap)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
import java.util.*;
classSolution { publicintfindKthLargest(int[] nums, int k) { PriorityQueue<Integer> minHeap = newPriorityQueue<>(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() > k) { minHeap.poll(); } } return minHeap.peek(); } }
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
1 2 3
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The largest rectangle is formed by bars with height 5 and 6, width = 2 → area = 10.
Example 2
1 2
Input: heights = [2,4] Output: 4
💡 Intuition
We want to find the largest rectangle area in a histogram. A monotonic increasing stack helps track the left and right boundaries for each bar:
Traverse the bars.
While current height is less than the top of stack, pop from stack and calculate area.
Area = poppedHeight * (currentIndex - stackTopAfterPop - 1).
Push current index onto the stack.
Add sentinel 0 at the end to flush out remaining bars.