What exactly is an array?

An array is a collection of elements of the same data type, stored in contiguous memory locations.

Because an array stores elements in contiguous memory locations, it allows direct (or random) indexing.

In an array, every element can be accessed directly using its index, like this:

array[i] = base_address + (i* size_of_element)

• base_address is the memory location of the first element
• i is the index
• size_of_element is the size of each element in bytes

This formula is possible only because all elements are of the same type and stored without gaps — that's what makes direct indexing fast and efficient.

This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element
of the array (generally denoted by the name of the array). The base value is index 0 and the difference between the two indexes is the offset.

• It is linear data structure

Techniques

1️⃣ Difference Array Technique

When solving data structure problems that involve frequent range updates, a naive solution often leads to Time Limit Exceeded (TLE). The Difference Array technique is a simple yet powerful tool that optimizes such problem by reducing time complexity from O(q * n) to O(q + n)

Why Do We Need It?

Consider the following problem:

You are given an array of size n initialized to 0. You are also given q operations. Each operation adds a value v to all elements in the range [L, R]. After all operations, output the final array.

Naive Approach:

We would just iterative over the array adding the value v in the range for every query.

for (int i = L; i <= R; i++) {
    A[i] += v;
}

Time Complexity per query = O(R - L + 1)

Total Time = O(q * n) in the worst case → ❌ inefficient for large n and q.

Difference Array to the Rescue → Optimizes the update to O(1) time.

2️⃣ Prefix Sum Technique

Suppose you're given an array of integers, and you're asked to return the sum of elements in a given range, say from index 2 to index 4.

A natural approach would be:

• Start at index 2
• Sum all the elements till index 4
• Return the result

Easy, right?

🤯 But Wait…

Now you're asked:

"What's the sum from index 4 to index 7?"

Again, you'd:

• Start from index 4
• Sum all the elements till index 7
• Return the result

And then again:

"What's the sum from index 3 to index 5?"

At this point, you're probably thinking:

"Ugh! Not again! Do I have to keep re-summing these numbers every time?"

Yes — if you stick to this method, you’re doing the same work over and over. This takes O(n) time for each query, and if you have q such queries, it becomes O(n × q) time overall.

💡 So You Think Smart…

You say:

"Why not just precompute the sum of elements up to each index — once — and reuse it?"

And that's where the prefix sum technique comes in.

✅ Solution: Prefix Sum

You create a new array called prefix, where:

prefix[i] = sum of all elements from index 0 to i
          = prefix[i - 1] + arr[i]

You build this once in O(n) time.

Now, to answer any query that asks for the sum from left to right, you simply do:

sum = prefix[right] - prefix[left - 1]

Why this works?

• prefix[right] gives the sum from index 0 to right
• prefix[left - 1] gives the sum from index 0 to left - 1
• Subtracting them gives the sum from left to right

Special Case:

If left == 0, then there's nothing to subtract – just return prefix[right].

Example:

Given array:

arr = [1, 2, 3, 4, 5, 6, 7]

Build prefix:

prefix[0] = 1
prefix[1] = 1 + 2 = 3
prefix[2] = 3 + 3 = 6
prefix[3] = 6 + 4 = 10
prefix[4] = 10 + 5 = 15
prefix[5] = 15 + 6 = 21
prefix[6] = 21 + 7 = 28

Now:

• Sum from index 2 to 4 = prefix[4] - prefix[1] = 15 - 3 = 12
• Sum from index 4 to 6 = prefix[6] - prefix[3] = 28 - 10 = 18

What is prefix sum array?

An array where each element at index i stores the sum of elements from index 0 to i of the original array.

How is prefix[i] computed?

prefix[0] = arr[0];
prefix[i] = prefix[i - 1] + arr[i];

How do you compute the sum from index L to R using prefix sum?

If L == 0 → sum = prefix[R];
sum = prefix[R] - prefix[L - 1];

What is the time and space complexity of prefix sum?

• Preprocessing:O(n)
• Query:O(1)
• Space:O(n)

Problems

1. Range Sum Query - Immutable: https://thejat.in/code/range-sum-query-immutable
2. Subarray Sum Equal to K: https://thejat.in/code/subarray-sum-equals-k
3. Subarray Sum Divisible by K: 

3️⃣ Two Pointers

• Opposite Ends: One pointer at the start, the other at the end (used for sorted arrays).
• Same Direction: Both pointers move from the start.
• Sliding Window: A variation where one or both pointers dynamically adjust.

Problems:

🟢 Easy