Advanced Array Techniques in DSA – Two Pointer, Sliding Window & Prefix Sum

Arrays (Advanced Techniques)

🚀 Introduction

If you already understand arrays, the next step is mastering advanced techniques that are heavily used in coding interviews.

👉 The 3 most important ones are:

• Two Pointer Technique
• Sliding Window
• Prefix Sum

---

🔹 1. Two Pointer Technique

💡 Concept

Use two pointers instead of one loop to reduce time complexity.

👉 Mostly used when:

• Array is sorted
• Finding pairs
• Removing duplicates

---

🧑‍💻 Example: Pair with Target Sum

<?phpfunction twoPointerSum($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;    while ($left < $right) {
        $sum = $arr[$left] + $arr[$right];        if ($sum == $target) {
            return "Found: $arr[$left], $arr[$right]";
        } elseif ($sum < $target) {
            $left++;
        } else {
            $right--;
        }
    }    return "Not Found";
}// Example
$arr = [1, 2, 3, 4, 6];
echo twoPointerSum($arr, 6);?>

---

⚡ Time Complexity

👉 O(n) (Better than O(n²))

---

🎯 Use Cases

• Pair sum problems
• Remove duplicates
• Container with most water

---

🔹 2. Sliding Window

💡 Concept

Instead of recalculating subarrays, we slide a window over the array.

👉 Best for:

• Subarray problems
• Fixed or variable window size

---

🧑‍💻 Example: Max Sum of Subarray (Size K)

<?phpfunction maxSumSubarray($arr, $k) {
    $windowSum = 0;
    $maxSum = 0;    // First window
    for ($i = 0; $i < $k; $i++) {
        $windowSum += $arr[$i];
    }    $maxSum = $windowSum;    // Slide window
    for ($i = $k; $i < count($arr); $i++) {
        $windowSum += $arr[$i] - $arr[$i - $k];
        $maxSum = max($maxSum, $windowSum);
    }    return $maxSum;
}// Example
$arr = [2, 1, 5, 1, 3, 2];
echo maxSumSubarray($arr, 3);?>

---

⚡ Time Complexity

👉 O(n) (instead of O(n*k))

---

🎯 Use Cases

• Maximum sum subarray of size K
• Longest substring problems
• Anagram problems

---

🔹 3. Prefix Sum

💡 Concept

Precompute sums to answer range queries quickly.

👉 Instead of recalculating sum every time:

• Store cumulative sum
• Answer queries in O(1)

---

🧑‍💻 Example: Range Sum Query

<?phpfunction prefixSum($arr) {
    $prefix = [];
    $prefix[0] = $arr[0];    for ($i = 1; $i < count($arr); $i++) {
        $prefix[$i] = $prefix[$i - 1] + $arr[$i];
    }    return $prefix;
}function rangeSum($prefix, $l, $r) {
    if ($l == 0) return $prefix[$r];
    return $prefix[$r] - $prefix[$l - 1];
}// Example
$arr = [1, 2, 3, 4, 5];
$prefix = prefixSum($arr);echo rangeSum($prefix, 1, 3); // Output: 9?>

---

⚡ Time Complexity

Operation	Complexity
Build Prefix	O(n)
Query	O(1)

---

🎯 Use Cases

• Range sum queries
• Subarray problems
• Competitive programming

---

🔥 Comparison

Technique	Best For	Complexity
Two Pointer	Pair problems	O(n)
Sliding Window	Subarrays	O(n)
Prefix Sum	Range queries	O(n) + O(1)

---