Chapters
Top 5 Array Interview Problems in Java (With Real-World Solutions)
Problem #5: Kadane’s Algorithm – Find Maximum Subarray Sum
🧠 Problem Statement
Given:
An array of integers (can include negatives).
Task:
Find the contiguous subarray with the maximum sum, and return
that sum.
🧾 Sample Input/Output
Input:
int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Output:
6
Explanation:
The subarray [4, -1, 2, 1] has the largest sum = 6
🔍 Brute Force Approach:
Check All Subarrays
public
static int maxSubarrayBrute(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
int sum = 0;
for (int j = i; j < arr.length; j++)
{
sum += arr[j];
max = Math.max(max, sum);
}
}
return max;
}
⛔ Time: O(n²)
✅
Works, but not scalable
✅ Kadane’s Algorithm – Optimal
Solution
public
static int maxSubarrayKadane(int[] arr) {
int maxSoFar = arr[0];
int currentMax = arr[0];
for (int i = 1; i < arr.length; i++) {
currentMax = Math.max(arr[i],
currentMax + arr[i]);
maxSoFar = Math.max(maxSoFar,
currentMax);
}
return maxSoFar;
}
✅ Time: O(n)
✅
Space: O(1)
✅
Elegant and powerful
🔍 How It Works
Kadane’s Algorithm keeps track of:
- currentMax:
best sum ending at current index
- maxSoFar:
best sum overall
At every step, you decide:
“Should I continue with current subarray or start new from
this element?”
🚀 Real Interview
Challenge #1: Track the Subarray Itself
public
static void maxSubarrayWithRange(int[] arr) {
int maxSoFar = arr[0], currentMax = arr[0];
int start = 0, end = 0, tempStart = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > currentMax + arr[i]) {
currentMax = arr[i];
tempStart = i;
} else {
currentMax += arr[i];
}
if (currentMax > maxSoFar) {
maxSoFar = currentMax;
start = tempStart;
end = i;
}
}
System.out.println("Max Sum: " +
maxSoFar);
System.out.println("Subarray: " +
Arrays.toString(Arrays.copyOfRange(arr, start, end + 1)));
}
✅ Outputs both sum and subarray
range
🧠 Edge Cases
|
Input |
Output |
Notes |
|
[1, 2, 3, 4] |
10 |
Whole array |
|
[-5, -2, -1, -3] |
-1 |
Just the least negative number |
|
[0, 0, 0, 0] |
0 |
Valid zero-sum |
|
[1, -2, 3, 4, -1] |
7 |
Mixed values |
🧨 Interview Variants
- "What
if you can remove one element?"
→ Track max prefix/suffix and test with one gap
→ Advanced dynamic programming - "What
if array is circular?"
→ Use standard Kadane for non-circular
→ Total sum - minimum subarray = circular max - "Print
all subarrays that give the max sum?"
→ Tricky — store all ranges matching maxSoFar
✅ Summary
|
Approach |
Time |
Space |
Use Case |
|
Brute Force |
O(n²) |
O(1) |
Small arrays |
|
Kadane’s |
O(n) |
O(1) |
Efficient and preferred |
|
Track Subarray |
O(n) |
O(1) |
If range is also needed |
FAQs
1. Why are array problems so common in Java interviews?
Because
they test core programming logic, data handling, loops, and algorithm
efficiency.
2. What’s the difference between int[] and Integer[] in Java?
int[] is a primitive array; Integer[] is an array of objects (wrappers). The latter allows null values and works with collections.
3. Is it better to use Arrays or ArrayLists in interviews?
For fixed-size problems, use arrays. For dynamic data, ArrayList is better — but stick to arrays unless otherwise asked
4. What are common pitfalls in Java array questions?
Index out of bounds, mutating arrays while iterating, and forgetting that Java arrays have fixed size.
5. How do I remove duplicates from a Java array?
Use a Set for uniqueness or sort the array first and remove duplicates in-place using two pointers.
6. When should I use the two-pointer technique?
It’s great for sorted arrays, especially for problems involving pair sums, removing duplicates, and reversing data in-place.
7. How can I rotate an array in Java?
Use reversal techniques or cyclic replacements to do it in O(1) space.
8. What’s the time complexity of array search vs binary search?
Linear search = O(n); binary search = O(log n), but only on sorted arrays.
9. How do I handle negative numbers or large input arrays?
Always consider edge cases: empty arrays, one element, all duplicates, etc. Optimize with hashmaps or prefix sums where needed.
10. What libraries or classes help with arrays in Java?
Use Arrays.sort(), System.arraycopy(), Arrays.toString(), and Collections when applicable — but show the manual solution first in interviews.
Comments(0)