Problem Statement

Given an integer array nums containing only 0, 1, and 2, sort the array in-place so that:

• 0 represents red
• 1 represents white
• 2 represents blue

The sorted order should be:

Constraints:

• Do not use built-in sort
• Must solve it in one pass
• Use constant extra space

This problem is also known as the Dutch National Flag Algorithm, designed by Edsger Dijkstra.

Example 1

Input

Output

Explanation

The array is rearranged so that:

• All 0s appear first
• All 1s appear next
• All 2s appear last

Example 2

Input

Output

Time & Space Complexity

Time Complexity: O(n)

The algorithm traverses the array only once using three pointers (low, mid, high). Each element is processed at most one time.

Space Complexity: O(1)

The sorting is done in-place, meaning no extra memory is used apart from a few pointer variables.

Number of Passes: Single Pass Traversal

The entire array is sorted in one traversal, making the solution highly efficient.

Explanation:

• We traverse the array only once
• Sorting happens in-place without extra memory

Problem Statement

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].

You must solve it without division and in O(n) time.

Approach

• Use two passes:

1. Left products: For each index, store the product of all elements to its left.
2. Right products: Traverse from the end, multiply each index with the product of all elements to its right.

• This way, each element gets the product of all elements except itself.

Complexity

• Time: O(n) – each element is processed twice.
• Space: O(1) extra (excluding output array).

Problem Statement

Given an integer array nums and an integer k, return the total number of continuous subarrays whose sum equals k.

Examples

Example 1

• Input: nums = [1, 2, 3], k = 3
• Output: 2
• Explanation: Subarrays [1,2] and [3] sum to 3.

Example 2

• Input: nums = [1, 1, 1], k = 2
• Output: 2
• Explanation: Subarrays [1,1] at positions (0,1) and (1,2).

Example 3

• Input: nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7
• Output: 4
• Explanation: Subarrays [3,4], [7], [7,2,-3,-3+1], [1,4,2].

Constraints

• 1≤nums.length≤105
• −104≤nums[i]≤104
• −109≤k≤109

Approach

• Use prefix sums with a hashmap:
• Keep a running sum while iterating.
• At each step, check if (current_sum - k) exists in the hashmap.
• If yes, add its frequency to the count (because those prefix sums form valid subarrays).
• Update hashmap with the current prefix sum.
• This avoids nested loops and works in O(n).

Complexity

• Time: O(n)
• Space: O(n)

Problem Statement

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in $O(n)$ time.

Examples

Example 1

Input: nums = [100, 4, 200, 1, 3, 2]

Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]

Output: 9

Explanation: The sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8].

Approach

Use a Hash Set for $O(1)$ lookups:

1. Insert all numbers into a Hash Set.
2. Iterate through the set. For each number, check if it's the start of a sequence by looking for num - 1.
3. If num - 1 is not present, start counting the length of the sequence by checking for num + 1, num + 2, etc.
4. Update the maximum length found so far.
5. This ensures each element is visited at most twice (once in the loop and once in the while count), maintaining linear time complexity.

Complexity

• Time: O(n)
• Space: O(n)

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i‑th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store.

Examples

Example 1

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

Output: 49

Explanation: The max area is between index 1 (height 8) and index 8 (height 7).

Area = min(8, 7) * (8 - 1) = 7 * 7 = 49.

Example 2

Input: height = [1, 1]

Output: 1

Approach: Two Pointers Technique

1. Initialize two pointers: left = 0, right = n - 1.
2. Width = (right - left).
3. Height = min(height[left], height[right]).
4. Area = width * height. Track the maximum.
5. Move the pointer pointing to the shorter line inward (to try for a taller line).
6. Repeat until left meets right.

Complexity

• Time: O(n) (single pass)
• Space: O(1) (constant extra space)

Problem Statement

You are given an array of intervals where intervals[i] = [start_i, end_i].

Merge all overlapping intervals and return an array of the non‑overlapping intervals that cover all the intervals in the input.

Example

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: Intervals [1,3] and [2,6] overlap, so they are merged into [1,6].

Example 2

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Constraints

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^4

Approach: Greedy + Sorting

1. Sort intervals by their start time.
2. Initialize a result list with the first interval.
3. Iterate through the sorted intervals:

• If the current interval overlaps with the last one in result (current.start <= last.end), merge them by updating the end to max(last.end, current.end).
• Otherwise, append the current interval to result.

1. Return the result list.

Complexity

• Time: O(n log n) (due to sorting)
• Space: O(n) (for storing merged intervals)

Problem Statement

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all elements in the subarray is strictly less than k.

Example

Example 1

Input: nums = [10, 5, 2, 6], k = 100

Output: 8

Explanation: The subarrays with product less than 100 are: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6].

Example 2

Input: nums = [1,2,3], k = 0

Output: 0

Approach: Sliding Window

1. Use two pointers (left and right) to maintain a sliding window.
2. Keep track of the product of elements inside the window.
3. Expand the window by moving right.
4. If the product becomes greater than or equal to k, shrink the window by moving left until the product is less than k.
5. At each step, the number of valid subarrays ending at right is (right - left + 1).
6. Accumulate this count.

Complexity

• Time: O(n) (each element visited at most twice)
• Space: O(1) (constant extra space)

Problem Statement

Given an integer array nums, rotate the array to the right by k steps, where k is non‑negative.

Example

Example 1

Input: nums = [1,2,3,4,5,6,7], k = 3

Output: [5,6,7,1,2,3,4]

Explanation: Rotate right by 3 steps → last 3 elements move to the front.

Example 2

Input: nums = [-1,-100,3,99], k = 2

Output: [3,99,-1,-100]

Approach: Reverse Technique

1. Normalize k → k = k % n (because rotating by n gives the same array).
2. Reverse the entire array.
3. Reverse the first k elements.
4. Reverse the remaining n - k elements.

This achieves rotation in‑place with O(n) time and O(1) extra space.

Problem Statement

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 a different day in the future to sell it.

Return the maximum profit you can achieve. If no profit is possible, return 0.

Example

Example 1

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

Input: prices = [7,6,4,3,1]

Output: 0

Explanation: No transaction is possible since prices keep decreasing.

Approach: Greedy + Tracking Minimum

1. Track the minimum price seen so far while iterating.
2. At each day, calculate the potential profit = currentPrice - minPrice.
3. Update the maximum profit if this profit is larger.
4. Return the maximum profit after traversing the array.

Complexity

• Time: O(n) (single pass)
• Space: O(1) (constant extra space)