DSA: Topic 1: Array

Why are arrays so important?

Around 30–40% of interview questions involve arrays, either directly or as the underlying data structure.

Companies don't ask:

"What is an array?"

They ask:

• Can you identify the right pattern?
• Can you optimise from O(n²) to O(n)?
• Can you write bug-free code?

---

What interviewers test

1. Traversal

Can you process every element exactly once?

Example:

nums = [4, 2, 8, 1]

Find the maximum.

Naive approach:

mx = nums[0]

for num in nums:
    if num > mx:
        mx = num

Time Complexity

O(n)

This is the expected solution.

---

2. Updating Values

Example

Increase every element by 10.

for i in range(len(nums)):
    nums[i] += 10

Interviewers want to know whether you understand when to modify a list in place versus creating a new one.

---

3. Searching

Suppose the interviewer asks:

Find whether 37 exists.

You scan once.

for num in nums:
    if num == 37:
        return True

Complexity

O(n)

A common follow-up is:

Can you do better?

If the array is sorted, you should think of Binary Search (O(log n)).

---

4. Insertion & Deletion Costs

Interviewers expect you to know these complexities without hesitation:

Operation	Complexity	Why?
Access arr[i]	O(1)	Direct indexing
Append	O(1) amortised	Usually adds to the end
Insert at front	O(n)	Elements shift right
Delete at front	O(n)	Elements shift left
Search	O(n)	May examine every element

Understanding why matters more than memorising the table.

---

The first optimisation interviewers expect

Consider this question:

Given an array, return the sum.

Most candidates write:

total = 0

for num in nums:
    total += num

That's perfectly fine.

However, if asked for:

Sum from index l to r for many different queries,

doing a loop each time is too slow. This leads to the Prefix Sum technique, where you preprocess once and answer each query in O(1). Interviewers often expect you to recognise when repeated work can be avoided.

---

The biggest interview lesson

Most array problems aren't about arrays—they're about recognising patterns.

For example:

Problem 1

Find two numbers whose sum equals a target.

Many candidates first think:

Check every pair

O(n²)

But interviewers expect you to recognise the Hash Map pattern and achieve:

O(n)

---

Problem 2

Move all zeros to the end.

Naive:

O(n²)

Expected:

O(n)

using the Two Pointers technique.

---

Problem 3

Longest substring without repeating characters.

Expected approach:

Sliding Window.

---

Most common array patterns

You should learn these in this order:

1. Simple traversal
2. Prefix Sum
3. Hashing
4. Two Pointers
5. Sliding Window
6. Binary Search on arrays
7. Sorting + scanning
8. Greedy on arrays

These patterns solve the majority of interview-style array questions.

---

Real interview questions to master

1. Two Sum
2. Best Time to Buy and Sell Stock
3. Contains Duplicate
4. Product of Array Except Self
5. Move Zeroes
6. Merge Sorted Array
7. Rotate Array
8. Maximum Subarray (Kadane's Algorithm)
9. Majority Element
10. Missing Number

If you can solve these confidently, you'll have a strong foundation in array problems.

How we'll learn

For each topic, we'll use the same structure:

1. Core concept (what you need to know)
2. How interviewers think (what they're testing)
3. Brute-force solution (often acceptable as a starting point)
4. Optimised solution (the expected answer)
5. Common mistakes and follow-up questions
6. 3–5 real interview problems, solved step by step in Python.

This approach mirrors how technical interviews are conducted and helps you build problem-solving skills rather than just memorising algorithms.