Mastering Prefix & Suffix Problems in DSA (with Java Code)

Prefix and suffix techniques are foundational in competitive programming and interview DSA problems. They allow us to preprocess arrays or strings for fast queries, range operations, and optimized solutions.

In this blog, we’ll explore the most asked prefix & suffix problems, break them down, and solve them in Java with clean code snippets.

🔹 1. Prefix Sum (Basic)

Problem: Given an array, answer multiple range sum queries efficiently.

Approach:

Precompute prefix sum array prefix[i] = prefix[i-1] + arr[i].
Answer range queries in O(1).

class PrefixSum {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10};
        int n = arr.length;

        int[] prefix = new int[n];
        prefix[0] = arr[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i-1] + arr[i];
        }

        // Query: sum from l to r
        int l = 1, r = 3; // 0-based index
        int sum = prefix[r] - (l > 0 ? prefix[l-1] : 0);
        System.out.println("Sum = " + sum); // 18
    }
}

🔹 2. Prefix Product (Handling Division-Free Subarray Product)

Problem: Find product of subarray without recomputing.

class PrefixProduct {
    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 5};
        int n = arr.length;

        int[] prefix = new int[n];
        prefix[0] = arr[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i-1] * arr[i];
        }

        int l = 1, r = 3;
        int product = prefix[r] / (l > 0 ? prefix[l-1] : 1);
        System.out.println("Product = " + product); // 60
    }
}

🔹 3. Prefix Max & Min (Sliding Ranges)

Problem: Precompute maximum/minimum from the left and right.

class PrefixMaxMin {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 6, 3};
        int n = arr.length;

        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];

        prefixMax[0] = arr[0];
        for (int i = 1; i < n; i++) {
            prefixMax[i] = Math.max(prefixMax[i-1], arr[i]);
        }

        suffixMax[n-1] = arr[n-1];
        for (int i = n-2; i >= 0; i--) {
            suffixMax[i] = Math.max(suffixMax[i+1], arr[i]);
        }

        System.out.println("PrefixMax[2] = " + prefixMax[2]); // 8
        System.out.println("SuffixMax[1] = " + suffixMax[1]); // 8
    }
}

🔹 4. Equilibrium Index (Prefix & Suffix Sum Trick)

Problem: Find index i where sum of left part equals right part.

class EquilibriumIndex {
    public static int findEquilibrium(int[] arr) {
        int total = 0;
        for (int x : arr) total += x;

        int leftSum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (leftSum == total - leftSum - arr[i]) {
                return i;
            }
            leftSum += arr[i];
        }
        return -1;
    }

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

🔹 5. Subarray Sum Equals K (Prefix Sum + HashMap)

Problem: Count number of subarrays whose sum equals k.

import java.util.*;

class SubarraySumK {
    public static int countSubarrays(int[] arr, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, count = 0;

        for (int x : arr) {
            sum += x;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

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

🔹 6. Trapping Rain Water (Prefix & Suffix Max)

Problem: Compute trapped water using prefix/suffix arrays.

class TrappingRainWater {
    public static int trap(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];

        left[0] = height[0];
        for (int i = 1; i < n; i++) {
            left[i] = Math.max(left[i-1], height[i]);
        }

        right[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            right[i] = Math.max(right[i+1], height[i]);
        }

        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.min(left[i], right[i]) - height[i];
        }
        return water;
    }

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

🔹 7. Product of Array Except Self (Prefix & Suffix)

Problem: Return product of array except self.

class ProductExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        int[] result = 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++) {
            result[i] = prefix[i] * suffix[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        int[] res = productExceptSelf(arr);
        for (int x : res) System.out.print(x + " "); // 24 12 8 6
    }
}

🔹 8. Suffix Array (String Problems)

Problem: Build suffix array for string searching & substring problems.

import java.util.*;

class SuffixArray {
    public static int[] buildSuffixArray(String s) {
        int n = s.length();
        String[] suffixes = new String[n];
        int[] suffixArr = new int[n];

        for (int i = 0; i < n; i++) {
            suffixes[i] = s.substring(i);
        }

        Arrays.sort(suffixes);
        for (int i = 0; i < n; i++) {
            suffixArr[i] = n - suffixes[i].length();
        }
        return suffixArr;
    }

    public static void main(String[] args) {
        String s = "banana";
        int[] sa = buildSuffixArray(s);
        System.out.println(Arrays.toString(sa));
        // Example output: [5, 3, 1, 0, 4, 2]
    }
}

🔹 9. Longest Prefix Suffix (KMP Algorithm)

Problem: Find longest proper prefix which is also suffix.

class LongestPrefixSuffix {
    public static int lps(String s) {
        int n = s.length();
        int[] lps = new int[n];
        int len = 0;

        for (int i = 1; i < n;) {
            if (s.charAt(i) == s.charAt(len)) {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len-1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps[n-1];
    }

    public static void main(String[] args) {
        String s = "abab";
        System.out.println(lps(s)); // 2
    }
}