These three array exercises each target a different pattern: one relies on prefix sums to track the best subarray sum, another reduces overlapping ranges by sorting and scanning, and the last rotates an array in place with a reversal trick. They are common building blocks for more complex problems, so they are worth working through until the techniques feel natural.
Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one element) with the largest sum and return that sum.
A subarray is a contiguous part of the array.
The approach uses a running prefix sum and the minimum prefix sum seen so far. For each element, update the running prefix sum, compute the difference against the smallest prefix sum encountered earlier, and keep the maximum difference as the answer. Then update the minimum prefix sum if the current prefix sum is smaller. This works because the best subarray ending at the current position equals the current prefix sum minus the lowest prefix sum before it.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = -inf
min_pre_sum = pre_sum = 0
for x in nums:
pre_sum += x
ans = max(ans, pre_sum - min_pre_sum)
min_pre_sum = min(min_pre_sum, pre_sum)
return ans
- Time complexity: O(n)
- Space complexity: O(1)
Merge Intervals
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of non-overlapping intervals that cover all the intervals in the input.
Example:
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].
Sort the intervals by their start value. Then scan them while maintaining a result list. If the current interval's start is less than or equal to the end of the last interval in the result, the two overlap; extend the last interval's end to the maximum of the two ends. Otherwise, append the current interval to the result.
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda p: p[0])
ans = []
for p in intervals:
if ans and p[0] <= ans[-1][1]:
ans[-1][-1] = max(ans[-1][1], p[1])
else:
ans.append(p)
return ans
- Time complexity: O(n log n) due to sorting
- Space complexity: O(n)
Rotate Array
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
The three-reversal method rotates the array in place. First reverse the entire array. Then reverse the first k elements. Finally reverse the remaining n - k elements. This produces the right rotation without extra space. Take k modulo n first to handle cases where k is larger than the array length.
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
def reverse(i: int, j: int) -> None:
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
n = len(nums)
k %= n
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
- Time complexity: O(n)
- Space complexity: O(1)
Summary
<table> <thead> <tr> <th>Problem</th> <th>Technique</th> <th>Time</th> <th>Space</th> </tr> </thead> <tbody> <tr> <td>Maximum Subarray</td> <td>Prefix sum + greedy</td> <td>O(n)</td> <td>O(1)</td> </tr> <tr> <td>Merge Intervals</td> <td>Sort + scan and merge</td> <td>O(n log n)</td> <td>O(n)</td> </tr> <tr> <td>Rotate Array</td> <td>Three reversals</td> <td>O(n)</td> <td>O(1)</td> </tr> </tbody> </table>These three problems appear frequently because they train interval reasoning, index manipulation, and in-place updates—skills that carry over to many other array tasks.