Welcome to Day 3 of your coding interview journey.

So far, we’ve covered:

• ✅ Day 1: HashMaps
• ✅ Day 2: Sliding Window

Today, we focus on one of the most fundamental topics in interviews:

👉 Arrays

Arrays are everywhere. And mastering them means mastering a huge portion of coding interview problems.

---

🧠 Why Arrays Matter

Most interview questions are built on arrays because they test:

• Problem-solving skills
• Optimization thinking
• Pattern recognition

---

🔑 Common Array Patterns

When working with arrays, look for:

• Prefix/Suffix computations
• Running sums
• Dynamic programming
• Greedy decisions

---

💡 Problem 1 – Product of Array Except Self

---

🧩 Problem

Given an integer array nums, return an array output such that:

output[i] is the product of all elements except nums[i]

⚠️ Constraints:

• You cannot use division
• Must run in O(n) time

---

❌ Brute Force

• For each element, multiply all others
  👉 Time Complexity: O(n²) (too slow)

---

✅ Optimal Approach – Prefix & Suffix Products

We compute:

• Prefix product (left side)
• Suffix product (right side)

---

🛠️ Solution in Python

def product_except_self(nums):
    n = len(nums)
    result = [1] * n

    # Prefix products
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # Suffix products
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

---

✅ Example

nums = [1, 2, 3, 4]
print(product_except_self(nums))

Output:

[24, 12, 8, 6]

---

⚡ Complexity

• Time: O(n)
• Space: O(1) (excluding output)

---

🧠 Key Insight

Instead of recomputing products, we reuse previous results.

👉 This is a prefix/suffix pattern, very common in interviews.

---

💡 Problem 2 – Maximum Subarray (Kadane’s Algorithm)

---

🧩 Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

---

❌ Brute Force

• Try all subarrays
  👉 Time Complexity: O(n²)

---

✅ Optimal Approach – Kadane’s Algorithm

This is a classic algorithm you must know.

---

🛠️ Solution in Python

def max_subarray(nums):
    current_sum = nums[0]
    max_sum = nums[0]

    for num in nums[1:]:
        # Decide whether to extend or restart
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)

    return max_sum

---

✅ Example

nums = [-2,1,-3,4,-1,2,1,-5,4]
print(max_subarray(nums))

Output:

6  # [4, -1, 2, 1]

---

🎯 Intuition Behind Kadane’s Algorithm

At each step, you decide:

👉 “Should I continue this subarray or start fresh?”

• If adding the current number improves the sum → continue
• Otherwise → start a new subarray

---

⚡ Complexity

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

---

⚠️ Common Mistakes

• ❌ Trying brute force first and not optimizing
• ❌ Forgetting edge cases (all negative numbers)
• ❌ Misunderstanding contiguous subarrays
• ❌ Using extra arrays unnecessarily

---

🧪 Practice Problems

To master arrays, try:

1. Best time to buy and sell stock
2. Maximum product subarray
3. Find minimum in rotated sorted array
4. Container with most water
5. Subarray sum equals K

---

🎯 Key Takeaways

• Arrays are the foundation of many problems
• Learn these patterns:
  • Prefix/Suffix
  • Kadane’s Algorithm
  • Greedy decisions
• Optimize from O(n²) → O(n) whenever possible

---

🚀 Your Challenge (Day 3)

Solve this:

Given an array, return the maximum product of a contiguous subarray.

(Hint: similar to Kadane’s, but trickier 😏)

---

📌 Final Thoughts

If you master arrays, you’re building a solid base for more advanced topics like:

• Dynamic Programming
• Graphs
• Greedy Algorithms

Keep going — you’re building real interview strength. 💪