Learn�DSA�Arrays & Strings

Lesson 5 � Intermediate-Advanced

Top Array Problems (LeetCode)

Module 01 ka last lesson hai ye. Yahan hum top 10 array problems dekhenge jo interviews mein sabse zyada puche jaate hain. Har problem ka solution aur approach samjhenge. Ye problems patterns pe based hain jo humne seekhe hain � two pointers, sliding window, prefix sum.

? 30 min✓ Intermediate-Advanced✓ All Module 01 topics

Problem-Solving Patterns Recap

Two Pointers

Sorted arrays mein pair finding, palindrome check, container problems. Left-right ya slow-fast pointer use karo. O(n) time.

Sliding Window

Contiguous subarray/substring problems. Fixed ya variable window. Subarray sum, max in window, anagram matching. O(n) time.

Prefix Sum

Range sum queries, subarray sum equals k, equal partitions. Precomputation se O(1) per query. Hash map se O(n).

Strategy: Har problem pe pehle ye socho � kya array sorted hai✓ Kya contiguous subarray chahiye✓ Kya range sum query hai✓ Pattern pehchanno aur approach select karo. Brute force mat karo seedha � optimize karo.

1. Two Sum (LeetCode #1)

Sabse pehla problem hai ye. Tumhe do numbers find karne hain jinka sum target ke barabar ho. Brute force O(n�) hai but hash map se O(n) ho jayega.

# Two Sum � Hash Map Approach
def two_sum(arr, target):
 seen = {} # value: index
 
 for i, num in enumerate(arr):
 complement = target - num
 
 if complement in seen:
 return [seen[complement], i]
 
 seen[num] = i
 
 return [-1, -1]

print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
Key Insight: Brute force mein har pair check karte ho � O(n�). Hash map mein sirf ek pass mein kaam ho jata hai � O(n). Har element ke liye bas check karo ki uska complement pehle aaya ya nahi.

2. Best Time to Buy and Sell Stock (LeetCode #121)

Tumhe prices array diya hai aur tumhe max profit nikalna hai ek transaction se (ek baar khareedo, ek baar becho). Ye problem minimum tracking pe based hai.

# Best Time to Buy and Sell Stock
def max_profit(prices):
 min_price = float('inf')
 max_profit = 0
 
 for price in prices:
 # Minimum price track karo ab tak
 min_price = min(min_price, price)
 
 # Current price pe bechna kitna fayda hoga
 profit = price - min_price
 max_profit = max(max_profit, profit)
 
 return max_profit

print(max_profit([7, 1, 5, 3, 6, 4])) # 5 (buy at 1, sell at 6)

Ek pass mein solve hota hai � min_price track karte jao aur har step pe profit calculate karo. Minimum price pe khareedna hai aur uske baad maximum price pe bechna hai. Ye greedy approach hai.

3. Contains Duplicate (LeetCode #217)

Check karo array mein koi duplicate element hai ya nahi. Hash set se O(n) time aur O(n) space mein solve hota hai.

# Contains Duplicate
def contains_duplicate(arr):
 seen = set()
 
 for num in arr:
 if num in seen:
 return True
 seen.add(num)
 
 return False

print(contains_duplicate([1, 2, 3, 1])) # True
print(contains_duplicate([1, 2, 3, 4])) # False

4. Product of Array Except Self (LeetCode #238)

Har element ke liye uske alawa sab elements ka product nikalo. Prefix aur suffix product use karo. O(n) time, O(1) extra space (output array).

# Product of Array Except Self
def product_except_self(arr):
 n = len(arr)
 result = [1] * n
 
 # Left pass: har position pe left side ka product
 left_product = 1
 for i in range(n):
 result[i] = left_product
 left_product *= arr[i]
 
 # Right pass: right side ka product multiply karo
 right_product = 1
 for i in range(n-1, -1, -1):
 result[i] *= right_product
 right_product *= arr[i]
 
 return result

print(product_except_self([1, 2, 3, 4])) # [24, 12, 8, 6]
Trick: Divide use mat karo (0 se divide nahi hota). Instead, left products aur right products alag se calculate karo aur multiply karo. Ye O(n) time mein hota hai bina extra space ke (sirf output array).

5. Maximum Subarray (LeetCode #53)

Kadane's Algorithm � ye DSA ka sabse famous algorithm hai. Contiguous subarray ka maximum sum nikalo. O(n) time mein solve hota hai.

# Maximum Subarray � Kadane's Algorithm
def max_subarray(arr):
 max_sum = arr[0]
 current_sum = arr[0]
 
 for i in range(1, len(arr)):
 # Current element lein ya purane sum mein add karein
 current_sum = max(arr[i], current_sum + arr[i])
 max_sum = max(max_sum, current_sum)
 
 return max_sum

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6
# Subarray: [4, -1, 2, 1]

Kadane's Algorithm ka logic hai � agar current sum negative ho jaye toh naya subarray shuru karo. Har element pe decide karo � kya current element better hai ya purane sum ke saath better hai.

6. Merge Intervals (LeetCode #56)

Intervals ko merge karo jo overlap karte hain. Pehle sort karo start time ke hisaab se, phir ek ek karke merge karo.

# Merge Intervals
def merge_intervals(intervals):
 intervals.sort(key=lambda x: x[0])
 merged = [intervals[0]]
 
 for current in intervals[1:]:
 last = merged[-1]
 
 if current[0] <= last[1]: # Overlap hai
 last[1] = max(last[1], current[1])
 else: # Naya interval add karo
 merged.append(current)
 
 return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6], [8,10], [15,18]]

7. Rotate Array (LeetCode #189)

Array ko k steps se rightward rotate karo. Three reverse technique use karo � O(n) time, O(1) space.

# Rotate Array � Three Reverse
def rotate_array(arr, k):
 n = len(arr)
 k = k % n # Handle k > n
 
 def reverse(start, end):
 while start < end:
 arr[start], arr[end] = arr[end], arr[start]
 start += 1
 end -= 1
 
 reverse(0, n-1) # Poora reverse karo
 reverse(0, k-1) # Pehle k elements reverse
 reverse(k, n-1) # Baaki elements reverse
 
 return arr

print(rotate_array([1,2,3,4,5,6,7], 3)) # [5,6,7,1,2,3,4]

8. Move Zeroes (LeetCode #283)

Sab zero elements ko end mein move karo bina order change kiye. Slow-fast pointer technique use karo.

# Move Zeroes
def move_zeroes(arr):
 slow = 0
 
 for fast in range(len(arr)):
 if arr[fast] != 0:
 arr[slow], arr[fast] = arr[fast], arr[slow]
 slow += 1
 
 return arr

print(move_zeroes([0, 1, 0, 3, 12])) # [1, 3, 12, 0, 0]

9. Missing Number (LeetCode #268)

0 se n tak ke numbers mein ek missing hai. XOR approach ya sum formula use karo � O(n) time, O(1) space.

# Missing Number � XOR Approach
def missing_number(arr):
 n = len(arr)
 xor_result = n # n bhi include karo
 
 for i in range(n):
 xor_result ^= i ^ arr[i]
 
 return xor_result

# Ya simple sum formula
def missing_number_sum(arr):
 n = len(arr)
 expected_sum = n * (n + 1) // 2
 actual_sum = sum(arr)
 return expected_sum - actual_sum

print(missing_number([3, 0, 1])) # 2

10. Trapping Rain Water (LeetCode #42)

Ye problem bahut famous hai. Bar chart ke beech paani kitna trap ho sakta hai ye nikalo. Two pointer approach O(n) time, O(1) space mein solve hoti hai.

# Trapping Rain Water � Two Pointer
def trap_rain_water(height):
 if not height:
 return 0
 
 left, right = 0, len(height) - 1
 left_max, right_max = height[left], height[right]
 water = 0
 
 while left < right:
 if left_max < right_max:
 left += 1
 left_max = max(left_max, height[left])
 water += left_max - height[left]
 else:
 right -= 1
 right_max = max(right_max, height[right])
 water += right_max - height[right]
 
 return water

print(trap_rain_water([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
Logic: Har position pe paani ka level = min(left_max, right_max) - current_height. Two pointer approach mein hum left aur right dono taraf se maximum track karte hain aur paani calculate karte hain. Ye O(n) time, O(1) space hai.

Try it: code khud likho




Exercise




Question: Given prices [7, 1, 5, 3, 6, 4], maximum profit find karo buy aur sell karke. Answer mein sirf maximum profit daalo.











Question: Given array [-2, 1, -3, 4, -1, 2, 1, -5, 4], maximum subarray sum nikalo using Kadane's Algorithm. Answer mein sirf maximum sum daalo.









Common mistakes




Module 01 complete!
Bahut badhiya! Arrays & Strings module complete ho gaya. Ab Module 02 (Linked Lists) shuru karte hain � ye arrays ka next level hai.