Day 4 · Topic 3
Greedy & Intervals
Greedy: make the locally optimal choice at each step. Works when greedy choice + optimal substructure holds (prove by contradiction or exchange argument). Intervals: always sort by start time first.
Medium Maximum Subarray (Kadane's)
INSIGHT: If current subarray sum goes negative, restart from next element. A negative prefix can never help a future subarray.
def maxSubArray(nums):
max_sum = curr = nums[0]
for n in nums[1:]:
curr = max(n, curr + n) # restart if curr went negative
max_sum = max(max_sum, curr)
return max_sum
# Time: O(n) | Space: O(1) Medium Jump Game I & II
# Jump Game I — Can you reach end?
def canJump(nums):
max_reach = 0
for i, n in enumerate(nums):
if i > max_reach: return False
max_reach = max(max_reach, i + n)
return True
# Jump Game II — Min jumps to reach end
def jump(nums):
jumps = curr_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == curr_end: # must jump here
jumps += 1
curr_end = farthest
return jumps
# Both: Time O(n) | Space O(1) Medium Merge Intervals
INSIGHT: Sort by start. If current interval's start ≤ last result's end → overlap, extend end. Otherwise add new interval.
def merge(intervals):
intervals.sort(key=lambda x: x[0])
result = [intervals[0]]
for start, end in intervals[1:]:
if start <= result[-1][1]: # overlap
result[-1][1] = max(result[-1][1], end)
else:
result.append([start, end])
return result
# Time: O(n log n) | Space: O(n) Medium Meeting Rooms II
INSIGHT: Min-heap tracks earliest-ending meeting. If new meeting starts after heap top ends → reuse room (heapreplace). Otherwise → new room.
import heapq
def minMeetingRooms(intervals):
intervals.sort(key=lambda x: x[0])
heap = [] # end times of ongoing meetings
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end) # reuse room
else:
heapq.heappush(heap, end) # new room
return len(heap)
# Time: O(n log n) | Space: O(n)