Campus Connect · Problem Board
Think. Solve. Connect.
Post your academic challenge, get solutions from peers. Every problem solved is a step towards mastery.
Every problem is a chance to grow
·
Peers helping peers
·
Build. Solve. Connect.
1
Total Problems
0
Solved
1
Open
1
Contributors
All Problems
1 result
CSE
Exam
medium
Longest Prefix Subarray with Given Sum (Java - Optimized Approach)
I am trying to solve a problem where I need to find the length of the longest subarray whose sum equals a given value K.
🔹 Problem Statement:
Given an integer array arr[] of size n and an integer K, return the length of the longest subarray whose sum is equal to K.
Example:
Input:
arr = [1, 2, 3, 1, 1, 1, 1]
K = 3
Output:
3
Explanation:
Subarray [1,1,1] has sum = 3 and length = 3 (maximum possible)
🔹 What I Tried:
First, I implemented a brute force approach using nested loops → O(n²)
Then I tried using prefix sum + HashMap to optimize to O(n)
🔹 My Approach (Optimized):
Maintain a running prefix sum
Use a HashMap to store (prefixSum → first occurrence index)
If (currentSum - K) exists in map → update max length
🔹 Issue / Doubt:
I am confused about:
When exactly to store prefix sum in HashMap
Why we store only the first occurrence
Handling edge case when prefix sum itself equals K
🔹 Expected Help:
Clear explanation of optimized approach
Step-by-step dry run
Best practices for prefix sum problems
open