Chapters
Top 5 Array Interview Problems in Java (With Real-World Solutions)
Problem #4: Find the Missing Number in a Sequence (1 to n)
🧠 Problem Statement
Given:
An array of size n - 1 containing distinct integers from 1 to n.
Task:
Find the missing number in the sequence.
🧾 Sample Input/Output
Input:
int[] arr = {1, 2, 4, 6, 3, 7, 8};
Output:
5
Explanation:
Numbers from 1 to 8 are expected. 5 is missing.
🔍 Naive Approach: Linear
Search for Every Element
Check for each number from 1 to n, whether it’s present.
public
static int findMissingNaive(int[] arr, int n) {
for (int i = 1; i <= n; i++) {
boolean found = false;
for (int j : arr) {
if (j == i) {
found = true;
break;
}
}
if (!found) return i;
}
return -1;
}
⛔ Time: O(n²)
⛔
Too slow for large arrays.
✅ Optimized Approach: Sum Formula
Sum of 1 to n = n * (n + 1) / 2
Subtract the actual sum to find the missing number.
public
static int findMissingSum(int[] arr, int n) {
int total = n * (n + 1) / 2;
int sum = 0;
for (int num : arr) {
sum += num;
}
return total - sum;
}
✅ Time: O(n)
✅
Space: O(1)
✅ XOR Approach (No Overflow Risk)
public
static int findMissingXOR(int[] arr, int n) {
int xor1 = 0, xor2 = 0;
for (int i = 1; i <= n; i++) xor1 ^= i;
for (int num : arr) xor2 ^= num;
return xor1 ^ xor2;
}
✅ Works even if values are large
(no overflow)
✅
Based on property: a ^ a = 0, and a ^ 0 = a
🧠 Edge Cases
|
Input |
Output |
Notes |
|
[2], n = 2 |
1 |
One missing at start |
|
[1, 2, 3, 5], n = 5 |
4 |
Middle missing |
|
[1, 2, 3, 4], n = 5 |
5 |
End missing |
|
[1, 2, 3, 4, 5], n = 5 |
❌ |
Nothing missing — validate input |
🚀 Real Interview
Challenge #1: Validate Input Before Searching
if
(arr.length != n - 1) {
throw new
IllegalArgumentException("Array size must be n - 1");
}
✅ Always sanitize input first —
interviewers love to test this.
🚀 Real Interview
Challenge #2: Find Missing and Duplicate (when one is repeated)
// e.g., [1, 2, 2, 4, 5] → missing = 3, repeated = 2
Use a frequency map or modify input using index marking
(advanced version)
🚀 Real Interview
Challenge #3: Return Missing Number Without Using Extra Space
You’ve already done it! ✅ XOR and SUM methods use O(1)
space
Use these to show optimization under memory constraints.
✅ Summary
|
Method |
Time |
Space |
Suitable For |
|
Brute Force |
O(n²) |
O(1) |
Not practical |
|
Sum Formula |
O(n) |
O(1) |
Simple, elegant, can overflow |
|
XOR Trick |
O(n) |
O(1) |
Fast, overflow-safe |
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)