Array Problems: A Code Reference Guide

Here are the notes for the array problems, complete with problem statements, complexities,
and code for your reference.

1. Find the largest and smallest element in an array

● Problem Statement: Find the largest and smallest values in an unsorted array.
● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];

public class Arrays1 {

public static int[] helperArray(int[] arr) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i : arr) {
if (i < min) {
min = i;
}
if (i > max) {
max = i;
}
}
return new int[]{max, min};
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
[Link]("Enter size of an array: ");
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
[Link]("Enter " + i + "th index value of an array : ");
 arr[i] = [Link]();
}
int[] output = helperArray(arr);
[Link]("largest Element is : " + output[0]);
[Link]("smallest Element is : " + output[1]);
}
}

2. Reverse an array in place

● Problem Statement: Reverse an array without using a new array.

● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];

public class Arrays2 {

public static void reverse(int[] nums) {
int s = 0;
int e = [Link] - 1;
while (s < e) {
int temp = nums[s];
nums[s] = nums[e];
nums[e] = temp;
s++;
e--;
}
return;
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
[Link]("enter size of an array: ");
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
[Link]("enter " + i + "th index value: ");
arr[i] = [Link]();
 }
reverse(arr);
for (int num : arr) {
[Link](num + " ");
}
}
}

3. Find the second largest element in an array

● Problem Statement: Find the second largest value in a given array.

● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];

public class Arrays3 {

public static int helper(int[] arr) {
if ([Link] < 2) return -1;
int max = Integer.MIN_VALUE;
int secondMax = Integer.MIN_VALUE;
for (int i : arr) {
if (i > max) {
secondMax = max;
max = i;
} else if (i > secondMax && i < max) {
secondMax = i;
}
}
return (secondMax == Integer.MIN_VALUE) ? -1 : secondMax;
}
public static void main(String[] args) {
[Link]("enter size of an array: ");
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
 [Link]("enter next value of index" + i + " : ");
arr[i] = [Link]();
}
int out = helper(arr);
[Link](out);
}
}

4. Move all zeroes to the end of the array

● Problem Statement: Rearrange an array so that all zeros are at the end, while
maintaining the relative order of non-zero elements.
● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];

public class Arrays4 {

public static void moveZeroEnd(int[] arr) {
int index = 0;
for (int i = 0; i < [Link]; i++) {
if (arr[i] != 0) {
arr[index] = arr[i];
index++;
}
}
while (index < [Link]) {
arr[index] = 0;
index++;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
[Link]("Enter size of array: ");
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
 [Link]("Enter element " + i + ": ");
arr[i] = [Link]();
}
moveZeroEnd(arr);
[Link]("Array after moving zeroes: ");
for (int i : arr) {
[Link](i + " ");
}
}
}

5. Rotate an array by k positions

● Problem Statement: Rotate an array to the left or right by k positions. The provided
code implements a left rotation.
● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];
public class Arrays5 {
public static void reverse(int[] arr, int s, int e){
while(s<e){
int temp=arr[s];
arr[s]=arr[e];
arr[e]=temp;
s++;
e--;
}
return;
}
public static int[] rotateK(int[] arr, int k){
int n=[Link];
k=k%n;
reverse(arr,0,k-1);
reverse(arr,k,n-1);
reverse(arr,0,n-1);
return arr;
 }
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
[Link]("Enter the value of k: ");
int k=[Link]();
[Link]("Enter size of an array: ");
int n=[Link]();
int[] arr=new int[n];
for(int i=0;i<n;i++){
[Link]("Enter value of "+i+"th value of array : ");
arr[i]=[Link]();
}
int[] nums = rotateK(arr,k);
for(int num:nums){
[Link](num + " ");
}
}
}

6. Find the missing number in an array of size n (1 to n)

● Problem Statement: Given an array containing n distinct numbers taken from 1, 2, ..., n,
find the one that is missing.
● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];
public class Arrays6 {
public static int findMissing(int[] arr){
int n=[Link];
int xor=0;
for(int i=1;i<=n+1;i++){
xor^=i;
if(i!=n+1){
xor^=arr[i-1];
}
}
 return xor;
}
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
[Link]("Enter the array size: ");
int n=[Link]();
int[] arr=new int[n-1];
for(int i=0;i<n-1;i++){
[Link]("enter the "+i+"th value of array: ");
arr[i]=[Link]();
}
int missing=findMissing(arr);
[Link](missing);
}
}

7. Find the duplicate number in an array

● Problem Statement: Find a number that appears more than once in an array.
● Time Complexity (TC): O(n log n)
● Space Complexity (SC): O(1) or O(log n)
● Code:
Java
import [Link];
import [Link];
public class Arrays7 {
public static int duplicate(int[] arr){
[Link](arr);
for(int i=1;i<[Link];i++){
if(arr[i]==arr[i-1]){
return arr[i];
}
}
return -1;
}
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
[Link]("Enter the size of an array: ");
 int n=[Link]();
int[] arr=new int[n];
for(int i=0;i<n;i++){
[Link]("Enter the value of element"+i+"th : ");
arr[i]=[Link]();
}
int num=duplicate(arr);
[Link]("duplicate element is : "+num);
}
}

8. Find the intersection of two arrays

● Problem Statement: Find the common elements between two arrays.

● Time Complexity (TC): O(n + m)
● Space Complexity (SC): O(min(n, m))
● Code:
Java
import [Link];
import [Link];
import [Link];
import [Link];
public class Arrays8 {
public static int[] intersection(int[] arr1,int[] arr2){
HashMap<Integer, Integer> mp=new HashMap<>();
int n=[Link];
int m=[Link];
ArrayList<Integer> num=new ArrayList<>();
for(int i=0;i<n;i++){
[Link](arr1[i],[Link](arr1[i],0)+1);
}
for(int i=0;i<m;i++){
if([Link](arr2[i])){
[Link](arr2[i],[Link](arr2[i])-1);
[Link](arr2[i]);
if([Link](arr2[i])<=0)[Link](arr2[i]);
}
}
 return [Link]().mapToInt(Integer::intValue).toArray();
}
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
[Link]("Enter size of 1st array: ");
int n=[Link]();
int[] arr1 =new int[n];
for(int i=0;i<n;i++){
[Link](i+"th value of an array: ");
arr1[i]=[Link]();
}
[Link]("Enter size of 2st array: ");
int m=[Link]();
int[] arr2 =new int[m];
for(int i=0;i<m;i++){
[Link](i+"th value of an array: ");
arr2[i]=[Link]();
}
int[] out=intersection(arr1,arr2);
[Link](out);
for(int i:out){
[Link](i+ " ");
}
[Link]();
}
}

9. Find the union of two arrays

● Problem Statement: Find all unique elements present in two arrays.

● Time Complexity (TC): O(n + m)
● Space Complexity (SC): O(n + m)
● Code:
Java
import [Link];
import [Link];
import [Link];
public class Arrays9 {
 public static int[] union(int[] arr1, int[] arr2){
HashSet<Integer> st=new HashSet<>();
int n= [Link];
int m= [Link];
if(n==0)return arr2;
if(m==0)return arr1;
for(int i=0;i<n;i++){
[Link](arr1[i]);
}
for(int i=0;i<m;i++){
[Link](arr2[i]);
}
return [Link]().mapToInt(Integer::intValue).toArray();
}
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
[Link]("Enter size of array 1: ");
int n=[Link]();
[Link]("\n");
int[] arr1=new int[n];
for(int i=0;i<n;i++){
[Link]("enter the "+i+"th value of an array: ");
arr1[i]=[Link]();
}
[Link]("Enter size of array 2: ");
int m=[Link]();
[Link]("\n");
int[] arr2=new int[m];
for(int i=0;i<m;i++){
[Link]("enter the "+i+"th value of an array: ");
arr2[i]=[Link]();
}
int[] nums = union(arr1, arr2);
for(int num:nums){
[Link](num+" ");
}
[Link]();
}
}
10. Kadane’s Algorithm: Maximum Subarray Sum

● Problem Statement: Find the contiguous subarray with the largest sum.
● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];

public class Arrays10 {

public static int MaxSubArray(int[] arr) {
int n=[Link];
int maxVaule=Integer.MIN_VALUE;
int sum =0;
for(int i=0;i<n;i++){
sum=[Link](sum+arr[i],arr[i]);
maxVaule=[Link](maxVaule, sum);
}
return maxVaule;
}
public static void main(String[] args) {
Scanner sc=new Scanner([Link]);
[Link]("Enter the size of an array: ");
int n=[Link]();
int[] arr=new int[n];
for(int i=0;i<n;i++){
[Link]("enter the "+i+"th value of an array: ");
arr[i]=[Link]();
}
int res=MaxSubArray(arr);
[Link]("Maximum subarray is : "+res);
}
}

11. Trapping Rainwater Problem

● Problem Statement: Calculate the total amount of water that can be trapped between
vertical bars of varying heights.
● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];

public class Arrays11 {

public static int trap(int[] height) {
int left = 0, right = [Link] - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
while (left <= right) {
if (height[left] <= height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
public static void main(String[] args) {
Scanner sc=new Scanner([Link]);
[Link]("Enter the size of an array: ");
int n=[Link]();
int[] arr=new int[n];
for(int i=0;i<n;i++){
[Link]("enter the "+i+"th value of an array: ");
arr[i]=[Link]();
}
 int res=trap(arr);
[Link]("Max water stored is :"+res);
}
}

12. Merge two sorted arrays without extra space

● Problem Statement: Merge two sorted arrays into one, without using any additional
space.
● Time Complexity (TC): O(n log n + m log m).
● Space Complexity (SC): O(1).
● Code:
Java
import [Link];
import [Link];

public class Arrays12 {

public static void mergeSort(int[] arr1, int[] arr2) {

int n=[Link];
int m=[Link];
int l=n-1;
int r=0;
while(l>=0 && r<m){
if(arr1[l]>arr2[r]){
int temp1=arr1[l];
arr1[l]=arr2[r];
arr2[r]=temp1;
}else{
break;
}
}
[Link](arr1);
[Link](arr2);
return;
}

public static void main(String[] args) {

 Scanner sc=new Scanner([Link]);
[Link]("Enter the size of an array 1: ");
int n=[Link]();
int[] arr1=new int[n];
for(int i=0;i<n;i++){
[Link]("enter the "+i+"th value of an array 1: ");
arr1[i]=[Link]();
}
[Link]("Enter the size of an array 2: ");
int m=[Link]();
int[] arr2=new int[m];
for(int i=0;i<m;i++){
[Link]("enter the "+i+"th value of an array 2: ");
arr2[i]=[Link]();
}
[Link]();
mergeSort(arr1,arr2);
[Link]("1st array");
for(int i=0;i<n;i++){
[Link]( arr1[i]+" ");
}
[Link]("\n 2nd array");
for(int i=0;i<m;i++){
[Link]( arr2[i]+" ");
}
}
}

String Problems: A Code Reference Guide

Here are the notes for the string problems, complete with problem statements, complexities,
and code for your reference.

1. Check if a string is a palindrome

● Problem Statement: Check if a given string is a palindrome (reads the same forwards
and backward), ignoring spaces and case.
● Time Complexity (TC): O(n)
● Space Complexity (SC): O(n) (for the character array)
● Code:
Java
import [Link];

public class String1 {

public static boolean checkPalindrome(String st){
st = [Link]("\\s+", "").toLowerCase();
char[] charArray= [Link]();
int n=[Link];
for(int i=0;i<n/2;i++){
if(charArray[i]!=charArray[n-i-1]){
return false;
}
}
return true;
}
public static void main(String[] args){
Scanner sc=new Scanner([Link]);
[Link]("enter the string : ");
String st=[Link]();
boolean ans= checkPalindrome(st);
[Link]("The given string is "+(ans?"a palindrom":"not a palindrom"));
[Link]();
}
}

2. Find the first non-repeating character in a string

● Problem Statement: Find the first character in a string that does not repeat.
● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];
 public class String2 {
public static int firstNonRepeatingIndex(String s) {
if (s == null || [Link]()) return -1;
int[] freq = new int[256];
for (int i = 0; i < [Link](); i++) {
freq[[Link](i)]++;
}
for (int i = 0; i < [Link](); i++) {
if (freq[[Link](i)] == 1) return i;
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String s = [Link]();
[Link]();
int idx = firstNonRepeatingIndex(s);
if (idx == -1) {
[Link](-1);
} else {
[Link]([Link](idx));
[Link](idx);
}
}
}

3. Count vowels and consonants in a string

● Problem Statement: Count the number of vowels and consonants in a given string.
● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];

public class String3 {

public static int[] countVowelsAndConsonants(String s) {
 int vowels = 0, consonants = 0;
s = [Link]();
for (int i = 0; i < [Link](); i++) {
char ch = [Link](i);
if ([Link](ch)) {
if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
vowels++;
else
consonants++;
}
}
return new int[]{vowels, consonants};
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
String s = [Link]();
[Link]();
int[] result = countVowelsAndConsonants(s);
[Link]("Vowels: " + result[0]);
[Link]("Consonants: " + result[1]);
}
}

4. Reverse words in a sentence

● Problem Statement: Reverse the order of words in a sentence.

● Time Complexity (TC): O(n)
● Space Complexity (SC): O(n)
● Code:
Java
import [Link];

public class String4 {

public static String reverseWords(String s) {
if (s == null || [Link]()) return "";
String[] words = [Link]().split("\\s+");
int left = 0, right = [Link] - 1;
 while (left < right) {
String temp = words[left];
words[left] = words[right];
words[right] = temp;
left++;
right--;
}
return [Link](" ", words);
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
[Link]("Enter a sentence to reverse its words: ");
String input = [Link]();
[Link]();
String reversed = reverseWords(input);
[Link]("Reversed sentence: " + reversed);
}
}

5. Check if two strings are anagrams

● Problem Statement: Determine if two strings are anagrams of each other (contain the
same characters with the same frequency).
● Time Complexity (TC): O(n)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];

public class String5 {

public static boolean areAnagrams(String s1, String s2) {
if ([Link]() != [Link]()) return false;
int[] freq = new int[256];
for (char c : [Link]()) {
freq[c]++;
}
for (char c : [Link]()) {
 freq[c]--;
if (freq[c] < 0) return false;
}
return true;
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
[Link]("Enter first string: ");
String s1 = [Link]();
[Link]("Enter second string: ");
String s2 = [Link]();
[Link]();
if (areAnagrams(s1, s2)) {
[Link]("✅ The strings are anagrams.");
} else {
[Link]("❌ The strings are NOT anagrams.");
}
}
}

6. Longest common prefix among words

● Problem Statement: Find the longest common prefix string amongst an array of
strings. If there is no common prefix, return an empty string.
● Time Complexity (TC): O(n * m) where n is the number of strings and m is the
average length of the strings.
● Space Complexity (SC): O(1) as no extra data structures are used.
● Code:

package Strings;

import [Link];

//18. Longest common prefix among words.🧠

//⏱ Complexity

//Time Complexity (TC): O(n * m) → compare all strings

//Space Complexity (SC): O(1) → no extra structures

public class String6 {

// Function to find longest common prefix

public static String longestCommonPrefix(String[] strs) {

if (strs == null || [Link] == 0) return "";

String prefix = strs[0]; // start with first string

for (int i = 1; i < [Link]; i++) {

// Shrink prefix until it matches the start of strs[i]

while (strs[i].indexOf(prefix) != 0) {

prefix = [Link](0, [Link]() - 1);

if ([Link]()) return "";

return prefix;

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);

[Link]("Enter number of words: ");

int n = [Link]();

[Link](); // consume newline

String[] words = new String[n];

for (int i = 0; i < n; i++) {

[Link]("Enter word " + (i+1) + ": ");

 words[i] = [Link]();

[Link]();

String lcp = longestCommonPrefix(words);

[Link]("Longest Common Prefix: " + ([Link]() ? "None" : lcp));

7. Longest Palindromic Substring

● Problem Statement: Find the longest substring in a given string that is a palindrome.
● Time Complexity (TC): O(n²)
● Space Complexity (SC): O(1)
● Code:
Java
import [Link];

public class String7 {

public static String longestPalindrome(String s) {
if (s == null || [Link]() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < [Link](); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = [Link](len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
 return [Link](start, end + 1);
}

private static int expandAroundCenter(String s, int left, int right) {

while (left >= 0 && right < [Link]() && [Link](left) == [Link](right)) {
left--;
right++;
}
return right - left - 1;
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
[Link]("Enter a string: ");
String input = [Link]();
String result = longestPalindrome(input);
[Link]("Longest Palindromic Substring: " + result);
}
}

8. Find all permutations of a string

● Problem Statement: Generate all possible permutations of a string.

● Time Complexity (TC): O(n × n!)
● Space Complexity (SC): O(n)
● Code:
Java
import [Link];
import [Link];

public class String8 {

public static void permute(String str, int l, int r) {
if (l == r) {
[Link](str);
return;
}
for (int i = l; i <= r; i++) {
str = swap(str, l, i);
 permute(str, l + 1, r);
str = swap(str, l, i);
}
}

private static String swap(String str, int i, int j) {

char[] charArray = [Link]();
char temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return [Link](charArray);
}

public static void permuteUnique(char[] chars, boolean[] visited, StringBuilder current) {

if ([Link]() == [Link]) {
[Link]([Link]());
return;
}
for (int i = 0; i < [Link]; i++) {
if (visited[i]) continue;
if (i > 0 && chars[i] == chars[i - 1] && !visited[i - 1]) continue;
visited[i] = true;
[Link](chars[i]);
permuteUnique(chars, visited, current);
[Link]([Link]() - 1);
visited[i] = false;
}
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
[Link]("Enter a string: ");
String input = [Link]();
[Link]("All permutations are:");
permute(input, 0, [Link]() - 1);
char[] chars = [Link]();
[Link](chars);
[Link]("All unique permutations are:");
permuteUnique(chars, new boolean[[Link]], new StringBuilder());
}
}
Approach 2: :0r using Sort+ first and last compare :

⏱ Complexity Analysis
● Time Complexity (TC):

○ Sorting → O(n log n) (n = number of strings, comparison cost depends on

string length)

○ Compare first & last string → O(m) (m = length of prefix)

○ Overall: O(n log n * m)

● Space Complexity (SC):

○ O(1) (ignoring sorting space, or O(n) depending on sort implementation)

package Strings;
import [Link];
import [Link];
public class String6_Approach3 {
// Function to find LCP between two strings
public static String commonPrefix(String s1, String s2) {
int minLen = [Link]([Link](), [Link]());
int i = 0;
while (i < minLen && [Link](i) == [Link](i)) {
i++;
}
return [Link](0, i);
}

// Function to find LCP among all strings using sort

public static String longestCommonPrefix(String[] strs) {
 if (strs == null || [Link] == 0) return "";

[Link](strs); // sort array lexicographically

return commonPrefix(strs[0], strs[[Link] - 1]);
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
[Link]("Enter number of words: ");
int n = [Link]();
[Link](); // consume newline

String[] words = new String[n];

for (int i = 0; i < n; i++) {
[Link]("Enter word " + (i+1) + ": ");
words[i] = [Link]();
}
[Link]();

String lcp = longestCommonPrefix(words);

[Link]("Longest Common Prefix: " + ([Link]() ? "None" : lcp));
}
}