Array Problems - Placement Revision Notes
Part 1 — Basic Array Problems
1. Find the Smallest Number in an Array
Sample Input
5
12 4 8 1 10
Sample Output
Start with the first element as the minimum. Compare every element with the current minimum and
update it whenever a smaller element is found.
public class Main {
public static void main(String[] args) {
int[] arr = {12,4,8,1,10};
int min = arr[0];
for(int i=1;i<[Link];i++){
if(arr[i] < min){
min = arr[i];
}
}
[Link](min);
}
}
Time: O(n) Space: O(1)
2. Find the Largest Number in an Array
Sample Input
5
12 4 8 1 10
Sample Output
12
Keep the first element as the largest and update it whenever a larger value is found.
public class Main {
public static void main(String[] args) {
int[] arr={12,4,8,1,10};
int max=arr[0];
for(int i=1;i<[Link];i++){
if(arr[i]>max){
max=arr[i];
}
}
[Link](max);
}
}
Time: O(n) Space: O(1)
3. Second Smallest and Second Largest
Sample Input
5
4 2 7 1 9
Output
Second Smallest = 2
Second Largest = 7
Maintain four variables: smallest , secondSmallest , largest , secondLargest , and update them while
traversing the array once.
public class Main {
public static void main(String[] args) {
int[] arr={4,2,7,1,9};
int smallest=Integer.MAX_VALUE;
int secondSmallest=Integer.MAX_VALUE;
int largest=Integer.MIN_VALUE;
int secondLargest=Integer.MIN_VALUE;
for(int num:arr){
if(num<smallest){
secondSmallest=smallest;
smallest=num;
}
else if(num<secondSmallest && num!=smallest){
secondSmallest=num;
}
if(num>largest){
secondLargest=largest;
largest=num;
}
else if(num>secondLargest && num!=largest){
secondLargest=num;
}
[Link](secondSmallest);
[Link](secondLargest);
}
}
Time: O(n) Space: O(1)
4. Reverse an Array
Sample Input
1 2 3 4 5
Output
5 4 3 2 1
Use two pointers: left starts at 0, right starts at n−1, swap until they meet.
import [Link];
public class Main {
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int left=0;
int right=[Link]-1;
while(left<right){
int temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
left++;
right--;
}
[Link]([Link](arr));
}
}
Time: O(n) Space: O(1)
5. Count Frequency of Each Element
Sample Input
1 2 1 3 2 2 5
Output
1 -> 2
2 -> 3
3 -> 1
5 -> 1
Store every element and its count inside a HashMap.
import [Link].*;
public class Main {
public static void main(String[] args) {
int[] arr={1,2,1,3,2,2,5};
HashMap<Integer,Integer> map=new HashMap<>();
for(int num:arr){
[Link](num,[Link](num,0)+1);
}
for(int key:[Link]()){
[Link](key+" -> "+[Link](key));
}
}
}
Time: O(n) Space: O(n)
Note: HashMap does not guarantee insertion or numeric order. For small positive integers it usually
happens to print in ascending order, but if you need a guaranteed order, use a TreeMap instead of
HashMap .
6. Rearrange Array in Increasing-Decreasing Order
Sample Input
8 7 1 6 5 9
Output
1 5 6 9 8 7
Sort the array, print the first half normally, then print the second half in reverse.
import [Link];
public class Main {
public static void main(String[] args) {
int[] arr={8,7,1,6,5,9};
[Link](arr);
int n=[Link];
for(int i=0;i<n/2;i++){
[Link](arr[i]+" ");
}
for(int i=n-1;i>=n/2;i--){
[Link](arr[i]+" ");
}
}
}
Time: O(n log n) Space: O(1)
7. Calculate Sum of Elements
Sample Input
1 2 3 4 5
Output
15
Traverse the array and keep adding every element.
public class Main {
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int sum=0;
for(int num:arr){
sum+=num;
}
[Link](sum);
}
}
Time: O(n) Space: O(1)
8. Average of Elements
Sample Input
1 2 3 4 5
Output
3.0
Average = Sum / Number of Elements
public class Main {
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int sum=0;
for(int num:arr){
sum+=num;
}
double avg=(double)sum/[Link];
[Link](avg);
}
}
Time: O(n) Space: O(1)
9. Find Median of Array
Sample Input
7 2 4 1 6
Output
Sort the array. Odd length → middle element. Even length → average of two middle elements.
import [Link];
public class Main {
public static void main(String[] args) {
int[] arr={7,2,4,1,6};
[Link](arr);
int n=[Link];
if(n%2==1){
[Link](arr[n/2]);
}
else{
double median=(arr[n/2]+arr[(n/2)-1])/2.0;
[Link](median);
}
}
}
Time: O(n log n) Space: O(1)
⭐ Part 1 Revision Cheat Sheet
Problem Algorithm Time Space
Smallest Element Linear Scan O(n) O(1)
Largest Element Linear Scan O(n) O(1)
Second Smallest/Largest Single Traversal O(n) O(1)
Reverse Array Two Pointers O(n) O(1)
Frequency Count HashMap O(n) O(n)
Increasing-Decreasing Sorting O(n log n) O(1)
Sum Traversal O(n) O(1)
Average Traversal O(n) O(1)
Median Sorting O(n log n) O(1)
These nine problems form a solid foundation for array questions commonly asked in placement tests and
coding interviews.
Part 2 — Array Manipulation Problems
10. Remove Duplicates from a Sorted Array
Sample Input
1 1 2 2 3 4 4 5
Sample Output
1 2 3 4 5
Since the array is sorted, duplicates are adjacent. Use two pointers ( i and j ).
public class Main {
public static void main(String[] args) {
int[] arr = {1,1,2,2,3,4,4,5};
int j = 0;
for(int i=1;i<[Link];i++){
if(arr[i]!=arr[j]){
j++;
arr[j]=arr[i];
}
}
for(int i=0;i<=j;i++){
[Link](arr[i]+" ");
}
}
}
Time: O(n) Space: O(1)
11. Remove Duplicates from an Unsorted Array
Sample Input
4 2 5 2 1 4 3
Sample Output
4 2 5 1 3
Use a LinkedHashSet to remove duplicates while preserving insertion order.
import [Link].*;
public class Main {
public static void main(String[] args) {
int[] arr={4,2,5,2,1,4,3};
LinkedHashSet<Integer> set=new LinkedHashSet<>();
for(int num:arr){
[Link](num);
}
for(int num:set){
[Link](num+" ");
}
}
}
Time: O(n) Space: O(n)
12. Insert an Element at Kth Position
Sample Input
Array : 1 2 3 4 5
Element : 10
Position : 3
Sample Output
1 2 10 3 4 5
Create a new array of size n+1.
public class Main {
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int pos=3;
int element=10;
int[] ans=new int[[Link]+1];
for(int i=0;i<pos-1;i++){
ans[i]=arr[i];
}
ans[pos-1]=element;
for(int i=pos-1;i<[Link];i++){
ans[i+1]=arr[i];
}
for(int num:ans){
[Link](num+" ");
}
}
}
Time: O(n) Space: O(n)
13. Move Zeroes to the End
Sample Input
0 1 0 3 12
Sample Output
1 3 12 0 0
Use a pointer j marking the next position to fill with a non-zero value. Traverse once and copy every
non-zero element forward, then fill the remaining tail with zeroes.
public class MoveZeroes {
public static void main(String[] args) {
int[] nums = {0, 1, 0, 3, 12};
int j = 0;
for (int i = 0; i < [Link]; i++) {
if (nums[i] != 0) {
nums[j] = nums[i];
j++;
}
}
while (j < [Link]) {
nums[j] = 0;
j++;
}
for (int x : nums) [Link](x + " ");
}
}
Time: O(n) Space: O(1)
14. Left Rotate Array by K Elements
Sample Input
1 2 3 4 5
k = 2
Sample Output
3 4 5 1 2
Reverse the first k elements, reverse the remaining elements, then reverse the whole array.
import [Link];
public class Main {
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int d=2;
int n=[Link];
d=d%n;
int start=0,end=d-1;
while(start<end){
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
start=d;
end=n-1;
while(start<end){
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
start=0;
end=n-1;
while(start<end){
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
[Link]([Link](arr));
}
}
Time: O(n) Space: O(1)
15. Right Rotate Array by K Elements
Sample Input
1 2 3 4 5
k = 2
Sample Output
4 5 1 2 3
import [Link];
public class Main {
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int d=2;
int n=[Link];
d=d%n;
int start=0,end=n-d-1;
while(start<end){
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
start=n-d;
end=n-1;
while(start<end){
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
start=0;
end=n-1;
while(start<end){
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
[Link]([Link](arr));
}
}
Time: O(n) Space: O(1)
16. Find Circular Rotation by K Positions
Sample Input
1 2 3 4 5
k = 2
Sample Output (Right Circular Rotation)
4 5 1 2 3
A circular rotation is the same as a left or right rotation where elements wrap around. The right-rotation
reversal algorithm from Problem 15 solves this optimally.
17. Rotate Array by K Elements (Using Temporary Array)
Sample Input
1 2 3 4 5
k = 2
Sample Output
3 4 5 1 2
public class Main {
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int d=2;
int n=[Link];
d=d%n;
int[] temp=new int[d];
for(int i=0;i<d;i++)
temp[i]=arr[i];
for(int i=d;i<n;i++)
arr[i-d]=arr[i];
for(int i=0;i<d;i++)
arr[n-d+i]=temp[i];
for(int num:arr)
[Link](num+" ");
}
}
Time: O(n) Space: O(k)
Note: this is the temporary-array approach, not the true Block Swap Algorithm. For most placement
interviews this solution is accepted unless the interviewer specifically asks for the Block Swap Algorithm.
⭐ Part 2 Revision Cheat Sheet
Problem Algorithm Time Space
Remove Duplicates (Sorted) Two Pointers O(n) O(1)
Remove Duplicates (Unsorted) LinkedHashSet O(n) O(n)
Insert at Kth Position New Array O(n) O(n)
Move Zeroes to End Two Pointers O(n) O(1)
Left Rotation Reversal Algorithm O(n) O(1)
Right Rotation Reversal Algorithm O(n) O(1)
Circular Rotation Reversal Algorithm O(n) O(1)
Rotate Using Temp Array Extra Array O(n) O(k)
These problems are among the most common array manipulation questions asked in placement tests and
coding interviews.
Part 3 — HashMap & Advanced Array Problems
18. Find All Repeating Elements
Sample Input
1 2 3 2 4 5 1
Sample Output
1 2
Store the frequency of each element in a HashMap. Print elements whose frequency is greater than 1.
import [Link].*;
public class Main {
public static void main(String[] args) {
int[] arr = {1,2,3,2,4,5,1};
HashMap<Integer,Integer> map = new HashMap<>();
for(int num : arr){
[Link](num, [Link](num,0)+1);
}
for(int key : [Link]()){
if([Link](key)>1){
[Link](key+" ");
}
}
}
}
Time: O(n) Space: O(n)
19. Find All Non-Repeating Elements
Sample Input
1 2 3 2 4 5 1
Sample Output
3 4 5
import [Link].*;
public class Main {
public static void main(String[] args) {
int[] arr={1,2,3,2,4,5,1};
HashMap<Integer,Integer> map=new HashMap<>();
for(int num:arr){
[Link](num,[Link](num,0)+1);
}
for(int key:[Link]()){
if([Link](key)==1){
[Link](key+" ");
}
}
}
Time: O(n) Space: O(n)
20. Find All Symmetric Pairs
Sample Input
(1,2)
(3,4)
(2,1)
(5,6)
(4,3)
Sample Output
(2,1)
(4,3)
import [Link].*;
public class Main {
public static void main(String[] args) {
int[][] arr={
{1,2},
{3,4},
{2,1},
{5,6},
{4,3}
};
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<[Link];i++){
int first=arr[i][0];
int second=arr[i][1];
if([Link](second) && [Link](second)==first){
[Link]("(" + first + "," + second + ")");
}
else{
[Link](first,second);
}
}
}
Time: O(n) Space: O(n)
21. Maximum Product Subarray
Sample Input
2 3 -2 4
Sample Output
Left & Right Traversal Approach.
public class Main {
public static void main(String[] args) {
int[] nums={2,3,-2,4};
int left=1;
int right=1;
int ans=Integer.MIN_VALUE;
int n=[Link];
for(int i=0;i<n;i++){
left*=nums[i];
right*=nums[n-1-i];
ans=[Link](ans,[Link](left,right));
if(left==0)
left=1;
if(right==0)
right=1;
[Link](ans);
}
}
Time: O(n) Space: O(1)
22. Replace Every Element by Its Rank
Sample Input
20 15 26 2 98 6
Sample Output
4 3 5 1 6 2
import [Link].*;
public class Main {
public static void main(String[] args) {
int[] arr={20,15,26,2,98,6};
int[] temp=[Link]();
[Link](temp);
HashMap<Integer,Integer> map=new HashMap<>();
int rank=1;
for(int num:temp){
if(){
[Link](num,rank++);
}
for(int num:arr){
[Link]([Link](num)+" ");
}
}
}
Time: O(n log n)
23. Sort Elements by Frequency
Sample Input
2 3 2 4 5 12 2 3 3 3 12
Sample Output
3 3 3 3 2 2 2 12 12 4 5
import [Link].*;
public class Main {
public static void main(String[] args) {
Integer[] arr={2,3,2,4,5,12,2,3,3,3,12};
HashMap<Integer,Integer> map=new HashMap<>();
for(int num:arr){
[Link](num,[Link](num,0)+1);
}
[Link](arr,(a,b)->{
if([Link](a)!=[Link](b))
return [Link](b)-[Link](a);
return a-b;
});
[Link]([Link](arr));
}
}
Time: O(n log n)
24. Finding Equilibrium Index
Sample Input
1 3 5 2 2
Sample Output
public class Main {
public static void main(String[] args) {
int[] arr={1,3,5,2,2};
int total=0;
for(int num:arr)
total+=num;
int left=0;
for(int i=0;i<[Link];i++){
total-=arr[i];
if(left==total){
[Link](i);
return;
}
left+=arr[i];
}
}
Time: O(n) Space: O(1)
25. Search an Element
Sample Input
1 2 3 4 5
Key = 4
Sample Output
Found at index 3
public class Main {
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int key=4;
for(int i=0;i<[Link];i++){
if(arr[i]==key){
[Link]("Found at index "+i);
return;
}
[Link]("Not Found");
}
}
Time: O(n)
26. Check if Array is a Subset of Another Array
Sample Input
A = {11,1,13,21,3,7}
B = {11,3,7,1}
Sample Output
true
import [Link].*;
public class Main {
public static void main(String[] args) {
int[] A={11,1,13,21,3,7};
int[] B={11,3,7,1};
HashSet<Integer> set=new HashSet<>();
for(int num:A){
[Link](num);
}
boolean subset=true;
for(int num:B){
if(){
subset=false;
break;
}
[Link](subset);
}
}
Time: O(n + m) Space: O(n)
27. Sort an Array According to Another Array
Sample Input
A = {2,1,2,5,7,1,9,3,6,8,8}
B = {2,1,8,3}
Sample Output
2 2 1 1 8 8 3 5 6 7 9
import [Link].*;
public class Main {
public static void main(String[] args) {
Integer[] A = {2,1,2,5,7,1,9,3,6,8,8};
int[] B = {2,1,8,3};
HashMap<Integer,Integer> freq = new HashMap<>();
for(int num : A){
[Link](num, [Link](num,0)+1);
}
ArrayList<Integer> ans = new ArrayList<>();
for(int num : B){
while([Link](num,0) > 0){
[Link](num);
[Link](num,[Link](num)-1);
}
}
ArrayList<Integer> rem = new ArrayList<>();
for(int key : [Link]()){
while([Link](key) > 0){
[Link](key);
[Link](key,[Link](key)-1);
}
}
[Link](rem);
[Link](rem);
[Link](ans);
}
}
Time: O(n log n)
Note on Corrections
Every code sample above was traced by hand against its stated sample input and output. All of them
produce the correct result as written — no logic errors were found in Problems 1–12 and 14–27.
The one change made in this revision is Problem 13 (Move Zeroes to the End), which now uses the
cleaner two-pass version supplied by the user (class MoveZeroes ): copy all non-zero elements forward
with a pointer j , then fill everything from j onward with zeroes. This is easier to reason about than the
original swap-based version and is the more commonly expected interview answer. Both versions are
logically correct, but this one is now the version kept in the notes.