Welcome to Week 1 of your DSA journey! This week focuses on building a strong foundation by mastering arrays, 2D matrices, hash maps, and recursion, along with 10 essential problem-solving patterns that will keep recurring throughout your DSA prep.

---

📘 Data Structures

1. Array

Arrays are the most basic and foundational data structure in programming. They are used to store elements in a contiguous block of memory, allowing constant-time access via index.

💡 Key Use Cases:

• Traversal

• Sorting

• Rotating or reversing

• Subarray computations (e.g., Kadane’s Algorithm)

• Dutch National Flag problem

✅ Example 1: Best Time to Buy and Sell Stock (LeetCode 121)

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

✅ Example 2: Maximum Subarray using Kadane’s Algorithm (LeetCode 53)

def maxSubArray(nums):
    max_sum = curr_sum = nums[0]
    for num in nums[1:]:
        curr_sum = max(num, curr_sum + num)
        max_sum = max(max_sum, curr_sum)
    return max_sum

---

2. 2D Array / Matrix

Matrices extend arrays into 2 dimensions, enabling grid-based computations such as image rotation, dynamic programming, and more.

💡 Key Use Cases:

• Matrix traversal

• Spiral order traversal

• Setting rows/columns to zero

• Rotating matrix in place

✅ Example: Set Matrix Zeroes (LeetCode 73)

def setZeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    row_set, col_set = set(), set()
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 0:
                row_set.add(i)
                col_set.add(j)
    for i in range(rows):
        for j in range(cols):
            if i in row_set or j in col_set:
                matrix[i][j] = 0

---

3. Hash Map (Python dict)

A hash map (dictionary in Python) allows for constant time insertions, deletions, and lookups using key-value pairs.

💡 Key Use Cases:

• Frequency counting

• 2Sum problems

• Prefix sum indexing

✅ Example: Two Sum (LeetCode 1)

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        diff = target - num
        if diff in seen:
            return [seen[diff], i]
        seen[num] = i

---

4. Recursion Stack

Though not explicitly a data structure, recursion uses the call stack to store execution state. It’s especially useful for problems with self-similar structure (e.g. trees, backtracking).

✅ Example: Print Numbers from 1 to N

def printNums(n):
    if n == 0:
        return
    printNums(n - 1)
    print(n)

---

🧠 Problem Solving Patterns & Techniques

✅ 1. Kadane’s Algorithm – Maximum Subarray Sum

🔍 Problem:

Find the contiguous subarray with the maximum sum.

📑 Steps:

1. Initialize current_sum and max_sum to first element

2. Iterate through the array

3. At each step, choose: current_sum = max(num, current_sum + num)

4. Update max_sum as the maximum of itself and current_sum

5. Return max_sum

🧮 Dry Run:

Input: [-2,1,-3,4,-1,2,1,-5,4]
Max Subarray: [4,-1,2,1] → Sum = 6

✅ Code:

def maxSubArray(nums):
    current_sum = max_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

---

✅ 2. Two Pointer Technique – Remove Duplicates

🔍 Problem:

Remove duplicates from a sorted array in-place.

📑 Steps:

1. Set i = 0, j = 1

2. While j < len(nums):

   • If nums[i] != nums[j]: increment i, set nums[i] = nums[j]

   • Always move j forward

3. Return i + 1 (length of unique array)

✅ Code:

def removeDuplicates(nums):
    if not nums:
        return 0
    i = 0
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    return i + 1

---

✅ 3. Sliding Window – Maximize Window

🔍 Problem:

Find longest subarray with at most k zero flips

📑 Steps:

1. Initialize left = 0

2. Move right through array

3. If nums[right] == 0, reduce k

4. If k < 0, move left forward and increase k if left element was 0

5. Track window length with right - left + 1

✅ Code:

def longestOnes(nums, k):
    left = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            k -= 1
        if k < 0:
            if nums[left] == 0:
                k += 1
            left += 1
    return right - left + 1

---

✅ 4. Dutch National Flag – Sort 0s, 1s, 2s

📑 Steps:

1. Initialize: low = mid = 0, high = len(nums) - 1

2. While mid <= high:

   • If nums[mid] == 0: swap with low, increment both

   • If nums[mid] == 1: move mid

   • If nums[mid] == 2: swap with high, decrement high

✅ Code:

def sortColors(nums):
    low = mid = 0
    high = len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

---

✅ 5. Recursion Basics

📑 Steps:

1. Define base case (e.g., if n == 0)

2. Make recursive call with smaller input

3. Do work before/after the call as needed

✅ Fibonacci Recursion:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

---

✅ 6. Prefix Sum

📑 Steps:

1. Initialize prefix list: prefix = [0]

2. Loop through array, build prefix[i+1] = prefix[i] + arr[i]

3. Range sum: prefix[j+1] - prefix[i]

✅ Code:

def computePrefix(nums):
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)
    return prefix

---

✅ 7. Sorting Techniques Summary

✅ 1. Bubble Sort

🔍 Intuition:

Repeatedly swap adjacent elements if they are in the wrong order. "Bubble up" the largest element to the end in each pass.

📑 Algorithm:

1. For every i from 0 to n-1:

   • For every j from 0 to n-i-2, if arr[j] > arr[j+1], swap them.

2. Repeat until no swaps are needed.

🧠 Complexity:

• Time: O(n²)

• Space: O(1)

• Stable: ✅ Yes

✅ Code:

pythonCopyEditdef bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

---

✅ 2. Selection Sort

🔍 Intuition:

Select the minimum element in the unsorted part and place it at the beginning.

📑 Algorithm:

1. Loop i from 0 to n-1

2. Find index min_idx of the smallest element from i to n-1

3. Swap arr[i] and arr[min_idx]

🧠 Complexity:

• Time: O(n²)

• Space: O(1)

• Stable: ❌ No

✅ Code:

pythonCopyEditdef selectionSort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

---

✅ 3. Insertion Sort

🔍 Intuition:

Insert each element into its correct position in the sorted portion on the left.

📑 Algorithm:

1. Loop i from 1 to n-1

2. Store key = arr[i], and shift all greater elements one position right

3. Place key in its correct sorted position

🧠 Complexity:

• Time: O(n²), but O(n) best case (already sorted)

• Space: O(1)

• Stable: ✅ Yes

✅ Code:

pythonCopyEditdef insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

---

✅ 4. Merge Sort (Optimal)

🔍 Intuition:

Divide the array into halves, recursively sort, then merge.

📑 Algorithm:

1. Divide array until size = 1

2. Merge two sorted arrays into one

🧠 Complexity:

• Time: O(n log n)

• Space: O(n)

• Stable: ✅ Yes

✅ Code:

pythonCopyEditdef mergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

---

✅ 5. Quick Sort (Optimal, In-Place)

🔍 Intuition:

Pick a pivot, partition array around it, then sort partitions recursively.

📑 Algorithm:

1. Choose pivot (typically last element)

2. Partition: place all elements smaller than pivot to left, greater to right

3. Recursively quick sort left and right partitions

🧠 Complexity:

• Time: O(n log n) average, O(n²) worst

• Space: O(log n)

• Stable: ❌ No

✅ Code:

pythonCopyEditdef quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

---

✅ 8. Matrix Traversals & Rotation

🔁 Spiral Traversal Steps:

• Top row → Right col → Bottom row → Left col

• Shrink boundaries, repeat

def spiralOrder(matrix):
    result = []
    top, bottom = 0, len(matrix)
    left, right = 0, len(matrix[0])
    while top < bottom and left < right:
        for i in range(left, right):
            result.append(matrix[top][i])
        top += 1
        for i in range(top, bottom):
            result.append(matrix[i][right - 1])
        right -= 1
        if top < bottom:
            for i in range(right - 1, left - 1, -1):
                result.append(matrix[bottom - 1][i])
            bottom -= 1
        if left < right:
            for i in range(bottom - 1, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    return result

🔁 Rotate Matrix 90° Clockwise:

1. Transpose matrix (swap i, j)

2. Reverse each row

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

---

✅ Summary

📦 Data Structures

---

🧠 Problem-Solving Patterns & Techniques

✍️ Stay consistent. Solve, analyze, and blog your learnings!