🚀 Blog 6: Prefix/Suffix Sum & Greedy — Expedia DSA Prep

Expedia often includes problems where prefix sums, suffix products, or greedy traversal give optimal solutions.
We’ll cover:

1. Product of Array Except Self
2. Gas Station (Can Complete Circuit)
3. Minimum Jumps to Reach End

---

🔹 Problem 1: Product of Array Except Self

Pattern: Prefix & Suffix Multiplication

📌 Given an array, return output where res[i] = product of all nums except nums[i].

import java.util.*;

public class ProductExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int[] prefix = new int[n];
        int[] suffix = new int[n];

        prefix[0] = 1;
        for (int i = 1; i < n; i++)
            prefix[i] = prefix[i - 1] * nums[i - 1];

        suffix[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--)
            suffix[i] = suffix[i + 1] * nums[i + 1];

        for (int i = 0; i < n; i++)
            res[i] = prefix[i] * suffix[i];

        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(productExceptSelf(new int[]{1,2,3,4})));
        // [24,12,8,6]
    }
}

✅ Time Complexity: O(N)
✅ Space Complexity: O(N) (can optimize to O(1) extra space)

---

🔹 Problem 2: Gas Station (Can Complete Circuit)

Pattern: Greedy with running total

📌 Given two arrays gas[i] and cost[i], find the starting station index if you can travel the full circuit, else -1.

public class GasStation {
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int totalTank = 0, currTank = 0, start = 0;

        for (int i = 0; i < gas.length; i++) {
            totalTank += gas[i] - cost[i];
            currTank += gas[i] - cost[i];

            if (currTank < 0) {
                start = i + 1;
                currTank = 0;
            }
        }
        return totalTank >= 0 ? start : -1;
    }

    public static void main(String[] args) {
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        System.out.println(canCompleteCircuit(gas, cost)); // 3
    }
}

✅ Time Complexity: O(N)

---

🔹 Problem 3: Minimum Jumps to Reach End

Pattern: Greedy Range Expansion

📌 Given an array nums where nums[i] = max steps from index i, return min jumps to reach last index.

public class MinJumps {
    public static int jump(int[] nums) {
        int jumps = 0, currEnd = 0, farthest = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);

            if (i == currEnd) {
                jumps++;
                currEnd = farthest;
            }
        }
        return jumps;
    }

    public static void main(String[] args) {
        int[] arr = {2,3,1,1,4};
        System.out.println(jump(arr)); // 2
    }
}

✅ Time Complexity: O(N)

---

📊 Expedia Prefix/Suffix + Greedy Key Insights

• Prefix/Suffix precomputation saves from recomputation (O(N²) → O(N)).
• Gas Station is a classic greedy must-know.
• Jump Game variants are frequent — knowing the greedy range method is crucial.

---

👉 In Blog 7, we’ll move into Heap & Priority Queue problems (Top K Frequent Elements, Merge K Sorted Lists, Find Median from Data Stream).