Array Programs in Java

In Java, an array is a linear data structure that has a collection of the same data type. These elements are stored in a contiguous memory location. In this section, we will discuss a variety of array programs, including array operations, manipulation, sorting, searching, etc.

1. Java program to find the sum of the array elements.

To find the sum of the array’s elements, first we have defined and declared an array. After that, we have defined a sum() method that adds array elements. Inside this method, the loop iterates over each element of the array and adds an element to the sum variable, repeatedly. In the main() method, we have called the sum() method that returns the sum of the array elements.

Example

class Main {
static int arr[] = { 7, 4, 10, 9, 13, 26 };
// method for the sum of elements
static int sum()
{
int i, sum = 0;
// Iterate through all elements and add them to the sum
for (i = 0; i < arr.length; i++)
sum += arr[i];
return sum;
}
public static void main(String[] args)
{
System.out.println(“The sum of the given array is: “+ sum());
}
}

Compile and Run

Output:

The sum of the given array is: 69

2. Java program to find the reverse of an array.

Reversing an array means writing an array from the last element to the first element. First, we have initializead an array. The loop iterates over the array until the array is reversed. We swap the first element with the last, the second with the second last, and so on. At last, we convert the array into a string and print the reversed array.

Example

import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
// Swap elements from start to end
for (int i = 0; i < arr.length / 2; i++) {
int t = arr[i];
arr[i] = arr[arr.length – 1 – i];
arr[arr.length – 1 – i] = t;
}
System.out.println(“” + Arrays.toString(arr));
}
}

Compile and Run

Output:

[5, 4, 3, 2, 1]

3. Java program to merge two arrays.

There are various ways to merge two arrays. But in this program, we have used user-defined logic to merge two arrays. This method is useful when we need full control over the merging process without relying on built-in functions. It directly merges the arrays.

Example

import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int arr1[] = { 23, 45, 56, 78, 90};
int arr2[] = { 3, 4, 6, 8, 9, 0, 7};
// determining the length of both arrays
int sizearr1 = arr1.length;
int sizearr2 = arr2.length;
// resultant array size
int sizearr3 = sizearr1 + sizearr2;
// Creating a new array
int[] arr3 = new int[sizearr3];
// Loop to store the elements of the first array into the resultant array
for (int i = 0; i < sizearr1; i = i + 1) {
// Storing the elements in the resultant array
arr3[i] = arr1[i];
}
// Loop to concatenate the elements of the second array into the resultant array
for (int i = 0; i < sizearr2; i = i + 1) {
// Storing the elements in the resultant array
arr3[sizearr1 + i] = arr2[i];
}
System.out.println(“” + Arrays.toString(arr3));
}
}

Compile and Run

Output:

[23, 45, 56, 78, 90, 3, 4, 6, 8, 9, 0, 7]

4. Java program to find the second most significant element in a sorted matrix.

In a sorted matrix, the rows and columns of the elements are placed in ascending order. We can navigate the matrix and note the largest and second-largest elements to determine the second-largest element. The second-largest element will have been stored when the traverse is complete.

The program uses a simple approach to find the second-largest element in a sorted matrix. It applies a nested loop to traverse the matrix in reverse order and compares each element with the largest and second-largest elements found so far. The program updates the largest and second-largest variables accordingly. Finally, it prints the value of the second-largest element.

Example

public class Main
{
public static void main(String[] args)
{
int[][] matrix =
{
{1,2,3},
{4,5,6},
{7,8,9}
};
int rows=matrix.length;
int cols=matrix[0].length;
int largest=matrix[rows-1][cols-1]; // Initialize largest with the bottom-right element
int secondLargest=matrix[rows-1][cols-2]; // Initialize secondLargest with the element before largest
// Traverse the matrix in reverse order
for (int i=rows-1;i>=0;i–)
{
for (int j=cols-1;j>=0;j–)
{
if (matrix[i][j]>largest)
{
secondLargest=largest; // Update secondLargest to the previous largest
largest=matrix[i][j]; // Update largest to the new largest element
}
else if(matrix[i][j]>secondLargest&&matrix[i][j]<largest)
{
secondLargest=matrix[i][j];
}
}
}
System.out.println(“Second largest element in the sorted matrix is: “+secondLargest);
}
}

Compile and Run

Output:

Second largest element in the sorted matrix is: 8

Complexity Analysis

Time Complexity: O(rows * cols), where rows and cols are the dimensions of the matrix.

Space Complexity: O(1), as we use constant additional space.

5. Java program to find the k-th smallest element in a sorted matrix.

In a sorted matrix, elements are arranged in ascending order, both row-wise and column-wise. The task is to find the kth smallest element in the matrix.

The program uses a min-heap implemented with a PriorityQueue to find the kth smallest element in a sorted matrix. The findKthSmallest() method initializes the minHeap and adds the elements from the first column. It then performs k-1 iterations, extracting the minimum element, finding its indices, and adding the next element from the same row to the minHeap. Finally, the method returns the kth smallest element. The main function showcases the method by providing a sample matrix and k value.

Example

import java.util.*;
public class Main
{
public static int findKthSmallest(int[][] matrix,int k)
{
int rows=matrix.length;
int cols=matrix[0].length;
PriorityQueue<Integer> minHeap=new PriorityQueue<>();
for (int i=0;i<rows;i++) {
minHeap.add(matrix[i][0]);
}
// Perform k-1 iterations
for (int i=0;i<k-1;i++)
{
int minElement=minHeap.poll(); // Extract the minimum element
// Get the row and column index of the extracted element
int rowIndex=-1;
int colIndex=-1;
for (int j=0;j<rows;j++)
{
for (int p=0;p<cols;p++)
{
if (matrix[j][p]==minElement)
{
rowIndex=j;
colIndex=p+1;
break;
}
}
}
// Add the next element from the same row to the min-heap
if (colIndex<cols) {
minHeap.add(matrix[rowIndex][colIndex]);
}
}
return minHeap.peek(); // Return the kth smallest element
}
public static void main(String[] args)
{
int[][] matrix={
{1,3,5},
{6,7,12},
{11,14,14}
};
int k=4;
int kthSmallest=findKthSmallest(matrix,k);
System.out.println(“The “+ k+”-th smallest element in the sorted matrix is: “+kthSmallest);
}
}

Compile and Run

Output:

The 4-th smallest element in the sorted matrix is: 6

Complexity Analysis

Time Complexity: The time complexity is O(k * log(rows)).

Space Complexity: The space complexity is O(rows) for storing the elements in the min-heap.

6. Java program to remove duplicate elements from a sorted array.

In a sorted array, duplicate elements may occur consecutively. To put off duplicates from a looked-after array, we need to adjust the array in-place, making sure that each detail appears as effective as soon as. The Java program removes duplicates from a sorted array using the “RemoveDuplicates” class. The method “removeDuplicates” returns the new length of the modified array without duplicates. It checks if the array is empty, initializes “nextUnique” to 1, and traverses the array starting from the second element. It assigns unique elements to the position of “nextUnique” and increments it. After the loop, “nextUnique” represents the new length. The “main” function showcases the method by printing the modified array.

Example

import java.util.*;
public class Main
{
public static int removeDuplicates(int[] nums)
{
int n=nums.length;
if (n==0)
{
return 0;
}
int nextUnique=1;
// Pointer to track the position of the next unique element
// Traverse the array starting from the second element
for (int current=1;current<n;current++)
{
// Compare the current element with the element at the next unique – 1
if (nums[current]!=nums[nextUnique-1])
{
nums[nextUnique]=nums[current]; // Assign current element to nextUnique position
nextUnique++; // Increment nextUnique
}
}
return nextUnique;
}
public static void main(String[] args)
{
int[] nums={1,1,2,2,3,4,4,5};
int length=removeDuplicates(nums);
System.out.print(“Modified Array: “);
for (int i=0;i<length;i++)
{
System.out.print(nums[i]+” “);
}
}
}

Compile and Run

Output:

Modified Array: 1 2 3 4 5

Complexity Analysis

Time Complexity is O(n), where n is the array’s element count.

Space complexity is O(1) since the array is modified directly without additional data structures.

7. Java program to find the frequency of each word in a string array.

We shall calculate the frequency of each word in a string array using a Java program. In a list of strings, we want to know how frequently each word appears. To calculate the frequency of each word in a string array, the program employs a hash map.

A simple approach separates each string into words, and the number of each word is then saved in the hash map. After initializing a blank HashMap, the program loops through each string in the array. It determines if a word is present in the HashMap for each one it encounters.

If it does, the frequency increases; if not, it is set to 1, and the word is added to the hash map. Finally, the program prints the word-frequency pairs stored in the HashMap. The approach efficiently tracks and counts the occurrences of each word, allowing for accurate frequency analysis of the words in the string array.

Example

import java.util.*;
public class Main
{
public static void main(String[] args)
{
String[] strings={“Hello world”,”Hello Java”,”Java is great”,”Java is powerful”}; // Create a HashMap to store word-frequency pairs
Map<String,Integer> frequencyMap=new HashMap<>();
for (String str:strings)
{
// Split the string into words using whitespace as the delimiter
String[] words=str.split(“\\s+”);
// Count the occurrences of each word
for (String word:words)
{
// Check if the word already exists in the HashMap
if (frequencyMap.containsKey(word))
{
// If it exists, increment its frequency by 1
frequencyMap.put(word,frequencyMap.get(word)+1);
} else {
// If it does not exist, add it to the HashMap with a frequency of 1
frequencyMap.put(word,1);
}
}
}
// Print the word-frequency pairs
for (Map.Entry<String, Integer> entry : frequencyMap.entrySet()) {
System.out.println(“Word: ” + entry.getKey() + “, Frequency: ” + entry.getValue());
}
}
}

Compile and Run

Output:

Word: Java, Frequency: 3
Word: world, Frequency: 1
Word: Hello, Frequency: 2
Word: powerful, Frequency: 1
Word: is, Frequency: 2
Word: great, Frequency: 1

Complexity Analysis

The time complexity is O(n*m), where n represents the number of strings within the array and m is the maximum common sort of phrase in every string.

The space complexity of the program is O(n), where n is the total wide variety of words inside the array.

8. Java program to find the missing number in a sorted array of consecutive integers.

Using the binary search method, we locate the missing integer in a sorted array of succeeding integers. The first detail’s index is low, and the remaining is high. We determine whether or not the missing integer is on the left or proper side of the array by computing the expected value for the middle element, which ought to be the same as the first element plus the centre index. The operation is repeated until there is only one element left in the search space, at which point we update low or high as necessary. The missing number will be the expected value at the index low.

Example

public class Main
{
public static int findMissingNumber(int[] nums)
{
int low=0;
int high=nums.length-1;
// Perform binary search
while (low<=high)
{
int mid=low+(high-low)/2;
int expectedValue=nums[0]+mid;
if (nums[mid]==expectedValue)
{
// Missing number lies in the right half
low=mid+1;
} else
{
// Missing number lies in the left half
high=mid-1;
}
}
// Return the missing number
return nums[0]+low;
}
public static void main(String[] args)
{
int[] nums={1,2,3,4,6,7,8,9};
int missingNumber=findMissingNumber(nums);
System.out.println(“Missing number: “+missingNumber);
}
}

Compile and Run

Output:

Missing number: 5

Complexity Analysis

Time Complexity: The binary search approach has a time complexity of O(log n), where n is the size of the array

Space Complexity: The program has a space complexity of O(1), only using a few variables to track the low, high, and mid indices and the expected value.

9. Java program to find the element that appears only once in an array.

The technique used to find the element that appears most effectively at least once in an array is primarily based on the XOR operation. By XORing all the factors within the array, the factors that seem a fair number of instances will cancel out, leaving only the detail that appears best once. To enforce this approach, we initialize a variable ‘unique’ to zero. Then, we iterate through each detail inside the array and XOR it with the ‘particular’ variable. The result is stored back in ‘unique.’ At the end of the iteration, ‘unique’ will hold the element’s value that appears only once.

Example

public class Main
{
public static int findUnique(int[] nums)
{
int unique=0;
for (int num:nums)
{
unique^=num; // XOR the current element with ‘unique’
}
return unique;
}
public static void main(String[] args)
{
int[] nums = {1,2,3,4,3,2,1};
int uniqueElement=findUnique(nums);
System.out.println(“The element that appears only once: ” + uniqueElement);
}
}

Compile and Run

Output:

The element that appears only once: 4

Complexity Analysis

Time Complexity: The time complexity of this technique is O(n), where n is the length of the array.

Space Complexity: The Space complexity is O(1) because we simplest use a single variable to keep the result.

10. Java program to check if an array is a palindrome.

To check if an array is a palindrome, we will use a pointer method where one pointer starts evolving at the start of the array and the alternative at the end. The elements are as compared to those suggestions, and we move them closer and nearer collectively until they meet at the centre. We conclude that the array is not a palindrome if the elements at any point at the pointers are not equal. Otherwise, if the loop completes without finding any unequal elements, then the array is a palindrome. The two-pointer approach allows us to efficiently check for palindromicity by eliminating the need for additional space.

Example

public class Main
{
public static boolean isPalindrome(int[] nums)
{
int left=0; // Initialize the left pointer at the beginning of the array
int right=nums.length-1; // Initialize the right pointer at the end of the array
while (left<=right) { // Continue the loop until the pointers meet or cross each other
if (nums[left]!=nums[right])
{
return false; // If the elements at the pointers are not equal, the array is not a palindrome
}
left++;
right–;
}
return true; // If the loop completes without finding unequal elements, the array is a palindrome
}
public static void main(String[] args) {
int[] nums={1,2,3,2,1};
boolean isPalindrome=isPalindrome(nums);
if (isPalindrome)
{
System.out.println(“The array is a palindrome.”);
}
else
{
System.out.println(“The array is not a palindrome.”);
}
}
}

Compile and Run

Output:

The array is a palindrome.

Complexity Analysis

The time complexity of the above approach is O(n), where n is the length of the array.

The space complexity is O(1) as we are not using any extra space.

11. Java program to shuffle elements of an array.

To shuffle the elements of an array, we use the Fisher-Yates shuffle algorithm is commonly used. The procedure ensures that each array’s item is randomly permuted. Starting with the final entry in the array, the process iterates through the array in reverse order to get started. Each time, the current element is added to the range of the remaining unshrunk elements to create a random index. The element at the current index is then swapped with the element at the randomly generated index. The swapping continues until the first element is reached, resulting in a shuffled array with elements in random order.

Example

import java.util.Random;
public class Main
{
public static void shuffle(int[] nums)
{
Random rand=new Random();
for (int i=nums.length-1;i>=1;i–)
{
int j=rand.nextInt(i+1);
// Swap the current element with the randomly selected element
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
public static void main(String[] args)
{
int[] nums = {1,2,3,4,5};
System.out.println(“Original array: “);
for (int num:nums)
{
System.out.print(num + ” “);
}
shuffle(nums);
System.out.println(“\nShuffled array: “);
for (int num:nums)
{
System.out.print(num + ” “);
}
}
}

Compile and Run

Output:

Original array:
1 2 3 4 5
Shuffled array:
5 2 1 3 4

Complexity Analysis

The time complexity of this technique is O(N), where N is the size of the array.

The space complexity is O(1) since we use a consistent quantity of extra space for the random variety.

12. Java program to check if two matrices are orthogonal.

To examine if two matrices are orthogonal, we evaluate the dot manufactured of corresponding rows or columns of the matrices. The matrices are said to be orthogonal if the dot product is 0 for all pairs. The algorithm iterates through the rows or columns, then calculates the dot product and returns false if any dot product is non-zero. It then checks for appropriate dimensions. If all dot products are zero, it returns true to indicate that the matrices are orthogonal.

Example

public class Main
{
public static boolean areMatricesOrthogonal(int[][] matrix1,int[][] matrix2)
{
int rows1=matrix1.length;
int cols1=matrix1[0].length;
int rows2=matrix2.length;
int cols2=matrix2[0].length;
// Check if matrices have compatible dimensions
if (rows1 != rows2 || cols1 != cols2) {
return false;
}
// Check the dot product for each row/column pair
for (int i=0;i<rows1;i++) {
int dotProduct = 0;
for (int j=0;j<cols1;j++) {
dotProduct += matrix1[i][j] * matrix2[i][j];
}
if (dotProduct!=0)
{
return false;
}
}
return true;
}
public static void main(String[] args) {
int[][] matrix1={{1,2},{3,4}};
int[][] matrix2={{0,1},{-1,0}};
boolean areOrthogonal = areMatricesOrthogonal(matrix1, matrix2);
if (areOrthogonal) {
System.out.println(“The matrices are orthogonal.”);
} else {
System.out.println(“The matrices are not orthogonal.”);
}
}
}

Compile and Run

Output:

The matrices are not orthogonal.

Complexity Analysis:

The time complexity of this technique is O(n), where n is the range of rows or columns in the matrices.

The space complexity is O(1), as no additional data structures are used.

13. Java program to find the maximum element in a two-dimensional array.

We initialize the variable ‘ max’ with the smallest value conceivable given the data type of the array elements to determine the greatest element in a two-dimensional array. The next step is to loop separately via the array’s rows and factors. Every element is compared to the modern fee of “max,” and if the detail is more, “max” is up to date. The maximum element in the two-dimensional array will be contained in ‘max’ once all items have been iterated through. By comparing each element to the current maximum value, the method enables us to determine the maximum element quickly.

Example

public class Main
{
public static int findMaximumElement(int[][] array) {
int max=Integer.MIN_VALUE; // Initialize max with the minimum value
for (int i=0;i<array.length;i++)
{
// Iterate through each element of the row
for (int j=0;j<array[i].length;j++)
{
// Compare the current element with the current max value
if (array[i][j] > max) {
max=array[i][j];
}
}
}
return max; // Return the maximum element
}
public static void main(String[] args) {
int[][] array={
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int maximum=findMaximumElement(array);
System.out.println(“The maximum element in the array is: “+maximum);
}
}

Compile and Run

Output:

The maximum element in the array is: 9

Complexity Analysis

The time complexity of this approach is O(n * m), where n is the number of rows and m is the number of columns in the two-dimensional array.

The space complexity is O(1) when you consider that we are not the usage of any extra area that grows with the entered size.

14. Java program to find the sum of each diagonal in a matrix.

To find the sum of each diagonal in a matrix, we iterate through the elements and calculate the diagonal index of every component by summing its row and column indices. We then add the element’s value to the corresponding diagonal sum in an array. After processing all elements, the array will contain the sum of each diagonal.

Example

public class Main {
public static int[] getDiagonalSums(int[][] matrix) {
int rows=matrix.length;
int cols=matrix[0].length;
int numDiagonals=rows+cols-1;
int[] sums=new int[numDiagonals];
for (int i=0;i<rows;i++) {
for (int j=0;j<cols;j++) {
int diagonalIndex=i+j;
sums[diagonalIndex]+=matrix[i][j];
}
}
return sums;
}
public static void main(String[] args) {
int[][] matrix={
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int[] diagonalSums=getDiagonalSums(matrix);
System.out.println(“Sum of each diagonal:”);
for (int sum:diagonalSums) {
System.out.println(sum);
}
}
}

Compile and Run

Output:

Sum of each diagonal:
1
6
15
14
9

Complexity Analysis

The approach has a time complexity of O(m*n), where m is the number of rows and n is the number of columns in the matrix.

The space complexity is O(m + n), as we must store the diagonal sums in an array.

15. Java program to find the element with the maximum frequency in an array.

We use a HashMap to record the frequency of each element in the array to locate the element with the highest frequency. The element with the highest frequency can be recognized via looping through the array and updating the frequency within the hash map. Then, by comparing the frequency counts in the HashMap, we identify the element with the maximum frequency. The approach allows us to efficiently find the element with the highest frequency in the array.

Example

import java.util.*;
public class Main {
public static int findMaxFrequencyElement(int[] nums) {
Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
return Collections.max(frequencyMap.entrySet(), Map.Entry.comparingByValue()).getKey();
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 2, 1, 2, 3, 3, 3};
System.out.println(“Element with maximum frequency is: ” + findMaxFrequencyElement(nums));
}
}

Compile and Run

Output:

Element with maximum frequency is: 3

Complexity Analysis

The time complexity of this technique is O(n), where n is the size of the array.

The area complexity is O(n) because a HashMap can save up to n unique elements in the worst case.

16. Java program to rotate a two-dimensional array clockwise.

To rotate a two-dimensional array clockwise, we can follow a two-step approach: transposing the array and reversing each row. First, we iterate via the array and switch each detail at function (i, j) with the detail at the role (j, i), then successfully transpose the array. After, we iterate through each row of the transposed array and reverse it by swapping the elements from the start and end of the row until they meet in the middle. The process rotates the array clockwise.

Example

public class Main {
public static void rotateClockwise(int[][] matrix) {
int rows=matrix.length;
int cols=matrix[0].length;
// Transpose the array
for (int i=0;i<rows;i++) {
for (int j=i;j<cols;j++) {
int temp=matrix[i][j];
matrix[i][j]=matrix[j][i];
matrix[j][i]=temp;
}
}
// Reverse each row
for (int i=0;i<rows;i++) {
int left=0;
int right=cols-1;
while (left<right) {
int temp=matrix[i][left];
matrix[i][left]=matrix[i][right];
matrix[i][right]=temp;
left++;
right–;
}
}
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
System.out.println(“Original Matrix:”);
printMatrix(matrix);
rotateClockwise(matrix);
System.out.println(“Rotated Matrix:”);
printMatrix(matrix);
}
public static void printMatrix(int[][] matrix) {
int rows=matrix.length;
int cols=matrix[0].length;
for (int i=0;i<rows;i++) {
for (int j=0;j<cols;j++) {
System.out.print(matrix[i][j]+” “);
}
System.out.println();
}
System.out.println();
}
}

Compile and Run

Output:

Original Matrix:
1 2 3
4 5 6
7 8 9

Rotated Matrix:
7 4 1
8 5 2
9 6 3

Complexity Analysis

The time complexity of this approach is O(n²), where n is the size of the array.

The space complexity is O(1) as we carry out the rotation in-place without using any additional storage systems.

17. Java program to sort a two-dimensional array across columns.

We construct a custom comparator that compares rows based on the required column to sort a two-dimensional array across columns. The Arrays.sort() method is called with the custom comparator as an argument. The sorting algorithm employs a comparator to compare rows according to the selected column and arrange them correctly. We can quickly sort the two-dimensional array across columns using this method.

Example

import java.util.Arrays;
import java.util.Comparator;
public class Main {
public static void sortByColumn(int[][] matrix, int column) {
// Use Arrays.sort() with a custom comparator to sort the matrix by the specified column
Arrays.sort(matrix,Comparator.comparingInt(row -> row[column]));
}
public static void main(String[] args) {
int[][] matrix = {
{13, 12, 11},
{6, 5, 4},
{19, 18, 17}
};
int columnToSortBy=1;
System.out.println(“Original Matrix:”);
printMatrix(matrix);
sortByColumn(matrix,columnToSortBy);
System.out.println(“Sorted Matrix by Column ” + columnToSortBy + “:”);
printMatrix(matrix);
}
public static void printMatrix(int[][] matrix) {
int rows=matrix.length;
int cols=matrix[0].length;
for (int i=0;i<rows;i++) {
for (int j=0;j<cols;j++) {
System.out.print(matrix[i][j]+” “);
}
System.out.println();
}
System.out.println();
}
}

Compile and Run

Output:

Original Matrix:
13 12 11
6 5 4
19 18 17

Sorted Matrix by Column 1:
6 5 4
13 12 11
19 18 17

Complexity Analysis

The time complexity of this approach is O(n log n), where n is the number of rows in the matrix.

The space complexity is O(1) since the sorting is done in place.

18. Java program to perform matrix exponentiation to compute Fibonacci numbers efficiently.

We might also describe the Fibonacci sequence as a matrix and calculate matrix multiplication to compute the Fibonacci numbers using matrix exponentiation speedily. The manner includes creating a transformation matrix that represents the Fibonacci series, utilizing matrix multiplication and exponentiation strategies, and then elevating the matrix to the necessary power using the powerMatrix approach. By deleting the Fibonacci number from the following matrix, we can also quickly calculate Fibonacci numbers.

Example

public class Main {
public static long computeFibonacci(int n) {
if (n<=0) {
return 0;
}
// Fibonacci transformation matrix
long[][] fibMatrix = {{1, 1}, {1, 0}};
// Raise fibMatrix to the power of (n-1)
fibMatrix = powerMatrix(fibMatrix, n – 1);
// Extract the Fibonacci number from the matrix
return fibMatrix[0][0];
}
private static long[][] powerMatrix(long[][] matrix, int power) {
if (power == 0) {
// Identity matrix
return new long[][]{{1, 0}, {0, 1}};
}
if (power == 1) {
return matrix;
}
long[][] result = powerMatrix(matrix, power / 2);
result = multiplyMatrices(result, result);
if (power % 2 != 0) {
result = multiplyMatrices(result, matrix);
}
return result;
}
private static long[][] multiplyMatrices(long[][] matrix1,long[][] matrix2) {
long[][] result=new long[2][2];
result[0][0]=matrix1[0][0]*matrix2[0][0]+matrix1[0][1]*matrix2[1][0];
result[0][1]=matrix1[0][0]*matrix2[0][1]+matrix1[0][1]*matrix2[1][1];
result[1][0]=matrix1[1][0]*matrix2[0][0]+matrix1[1][1]*matrix2[1][0];
result[1][1]=matrix1[1][0]*matrix2[0][1]+matrix1[1][1]*matrix2[1][1];
return result;
}
public static void main(String[] args) {
int n=10;
long fibonacci=computeFibonacci(n);
System.out.println(“Fibonacci number at position “+n+” is: “+fibonacci);
}
}

Compile and Run

Output:

Fibonacci number at position 10 is: 55

Complexity Analysis

The time complexity of this approach is O(log n) since we perform matrix multiplication using the exponentiation by squaring technique.

The space complexity is O(1) since we only need a fixed-size matrix and a few additional variables.

19. Given an array of integers, rearrange the array such that all even numbers appear before all odd numbers.

Note: Maintaining the relative order is not relevant for this problem.

We can use a two-pointer technique to reorder an array so that all even numbers appear before all odd numbers. While the right pointer begins at the end and advances backwards, the left pointer moves ahead from the beginning. The elements pointed by the left and right pointers are examined at each step, and swaps are made as needed. All even numbers will be arranged before odd numbers by the time the loop is complete.

Example

public class Main
{
public static void rearrangeArray(int[] arr)
{
int left=0;
int right=arr.length-1;
while (left<=right) {
if (arr[left]%2==0) {
left++; // Move the left pointer forward if the element is even
} else if (arr[right]%2==1) {
right–; // Move the right pointer backwards if the element is odd
} else {
swap(arr,left,right); // Swap the elements if the left element is odd and the right element is even
left++; // Move the left pointer forward
right–; // Move the right pointer backwards
}
}
}
public static void swap(int[] arr,int i,int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8,9};
System.out.println(“Original Array: “);
printArray(arr);
rearrangeArray(arr);
System.out.println(“Rearranged Array: “);
printArray(arr);
}
public static void printArray(int[] arr) {
for (int num:arr) {
System.out.print(num+” “);
}
System.out.println();
}
}

Compile and Run

Output:

Original Array:
1 2 3 4 5 6 7 8 9
Rearranged Array:
8 2 6 4 5 3 7 1 9

Complexity Analysis

The time complexity of this approach is O(n), where n is the number of elements in the array.

The space complexity is O(1) as we perform the rearrangement in place without using any additional data structures.

20. Java program to find the smallest missing positive number in an unsorted array.

We can rearrange the array by assigning each positive integer to its appropriate index to discover the smallest missing positive number in an unsorted array. You can accomplish this by looping through the array and switching each element with a positive integer with the one at the desired index. The array is iterated once more to locate the first index where an element no longer corresponds to the required value after the rearrangement. The index corresponds to the smallest missing positive number. If all elements match their desired values, the smallest missing positive number is the next positive integer after the array size.

Example

public class Main
{
public static int findSmallestMissingPositive(int[] nums)
{
int n=nums.length;
// Rearrange the array
for (int i=0;i<n;i++)
{
while (nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i])
{
swap(nums,i,nums[i]-1);
}
}
//Find the smallest missing positive number
for (int i=0;i<n;i++)
{
if (nums[i]!=i+1)
{
return i+1;
}
}
// If all elements match their desired values, return the next positive integer
return n+1;
}
public static void swap(int[] nums,int i,int j)
{
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
public static void main(String[] args)
{
int[] nums={3,4,-1,1};
int smallestMissingPositive = findSmallestMissingPositive(nums);
System.out.println(“Smallest Missing Positive Number: “+smallestMissingPositive);
}
}

Compile and Run

Output:

Smallest Missing Positive Number: 2

Complexity Analysis

The approach ensures a time complexity of O(n) and a space complexity of O(1) as we perform the rearrangement and search in place without additional data structures.

21. Java program to find the intersection of two arrays.

The best approach to finding the intersection of two arrays is to use a HashSet data structure. We create a HashSet and add all elements from one array to it. Then, we iterate through the second array and check if each element exists in the HashSet. If it does, we add it to the result ArrayList and remove it from the HashSet to avoid duplicates.

Example

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
public class Main{
public static List<Integer> intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set=new HashSet<>();
List<Integer> result=new ArrayList<>();
// Add elements of nums1 to the set
for (int num:nums1) {
set.add(num);
}
// Check for intersection in nums2
for (int num:nums2) {
if (set.contains(num)) {
result.add(num);
set.remove(num);
}
}
return result;
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 2, 1};
int[] nums2 = {2, 2};
List<Integer> intersection=intersection(nums1, nums2);
System.out.println(“Intersection: “+intersection);
}
}

Compile and Run

Output:

Intersection: [2]

Complexity Analysis

The time complexity of this approach is O(n), where n is the size of the larger array.

The space complexity is O(m), where m is the size of the HashSet.

22. Java program to find the longest subarray with an equal number of 0s and 1s.

Utilizing the prefix sum method, we can determine the longest subarray that contains an equal number of 0s and 1s. We can calculate the running sum while traversing the array by assigning a value of 1 for every 1 and -1 for every 0. When the running sum reaches zero, the number of 0s and 1s we have seen thus far is equal. To find the longest subarray, we store the running sum in a HashMap and its corresponding index. If the same running sum appears again, we update the maximum length by subtracting the stored index from the current index. By keeping track of the maximum length throughout the iteration, we can find the longest subarray with equal 0s and 1s.

Example

import java.util.HashMap;
public class Main {
public static int findMaxLength(int[] nums) {
int maxLength=0;
int runningSum=0;
HashMap<Integer,Integer> sumMap=new HashMap<>();
sumMap.put(0,-1); // Handle the case when the subarray starts from the beginning
for (int i=0;i<nums.length;i++) {
runningSum+=nums[i]==0?-1:1;
if (sumMap.containsKey(runningSum)) {
int startIndex=sumMap.get(runningSum);
maxLength=Math.max(maxLength,i-startIndex);
} else {
sumMap.put(runningSum,i);
}
}
return maxLength;
}
public static void main(String[] args) {
int[] nums = {0, 1, 0, 0, 1, 1, 0};
int maxLength=findMaxLength(nums);
System.out.println(“Length of the longest subarray with equal 0s and 1s is: “+maxLength);
}
}

Compile and Run

Output:

Length of the longest subarray with equal 0s and 1s: 6

Complexity Analysis

The time complexity of this approach is O(n) since we iterate through the array once.

The space complexity is O(n) as we store the running sum and its corresponding index in the HashMap.

23. Java program to find the maximum product of two integers in an array.

To find the maximum product of two integers in an array, we iterate through the array and keep track of the maximum and second maximum elements. We initialize max1 and max2 to the smallest possible integer values. Then, for each element, we compare it with max1 and update max2 and max1 accordingly. After iterating through the array, the maximum product is the product of max1 and max2, as max1 will hold the largest element and max2 will hold the second largest element.

Example

public class Main {
public static int findMaximumProduct(int[] arr) {
int max1=Integer.MIN_VALUE; // Initialize the maximum element to the smallest possible value
int max2=Integer.MIN_VALUE; // Initialize the second maximum element to the smallest possible value
for (int num:arr) {
if (num>max1) {
max2=max1; // Update the second maximum element
max1=num; // Update the maximum element
}
else if (num>max2) {
max2=num; // Update the second maximum element
}
}
return max1*max2; // Return the maximum product
}
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int maximumProduct=findMaximumProduct(arr);
System.out.println(“Maximum Product: “+maximumProduct);
}
}

Compile and Run

Output:

Maximum Product: 20

Complexity Analysis

The time complexity of this approach is O(n), where n is the size of the array.

The space complexity is O(1) since we only use constant extra space to store the maximum and second maximum elements.

24. Java program to find the smallest subarray length with a sum greater than a given value.

To find the smallest subarray length with a sum greater than a given value, we can utilize the sliding window technique. The approach involves maintaining a window that expands and contracts while calculating the current sum. We start with an empty window and gradually expand it by adding elements from the right end. If the current sum exceeds the given value, we update the minimum length of the subarray. Then, until the current total is less than or equal to the specified value, we contract the window from the left end by eliminating items. Until we reach the end of the array, we keep doing this.

Example

public class Main{
public static int findSmallestSubarray(int[] arr,int target) {
int minLength=Integer.MAX_VALUE; // Variable to store the minimum length of the subarray
int currentSum=0; // Variable to track the current sum of the subarray
int left=0; // Left pointer to mark the start of the subarray
int right=0; // Right pointer to mark the end of the subarray
while (right<arr.length) {
currentSum+=arr[right]; // Add the element at the right pointer to the current sum while (currentSum>target) {
minLength=Math.min(minLength,rightleft+1); // Update the minimum length if necessary
currentSum=arr[left]; // Subtract the element at the left pointer from the current sum
left++; // Move the left pointer to the right to contract the window
}
right++; // Move the right pointer to the right to expand the window
}
return (minLength==Integer.MAX_VALUE)?-1:minLength;
}
public static void main(String[] args) {
int[] arr={1, 4, 45, 6, 0, 19};
int target=51;
int smallestSubarrayLength=findSmallestSubarray(arr,target);
System.out.println(“Smallest Subarray Length: “+smallestSubarrayLength);
}
}

Compile and Run

Output:

Smallest Subarray Length: 3

Complexity Analysis

The time complexity of this approach is O(n), where n is the size of the array.

The space complexity is O(1) since we only use constant extra space to store variables.

25. Java program to find the triplet with the smallest sum in an array.

We can take the help of three variables (an integer array of size three will also do the work), and using a loop, we can find the minimum elements present in the given array. We will be looking for the minimum elements as we have to find the smallest sum.

Example

public class Main {
public static void findSmallestTripletSum(int[] arr) {
int n = arr.length; // finding the size
// for storing the first three minimum values present in the given array.
int fMin = Integer.MAX_VALUE;
int sMin = Integer.MAX_VALUE;
int tMin = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
// getting the first, second and third minimum elements
if (arr[i] < fMin) {
tMin = sMin;
sMin = fMin;
fMin = arr[i];
}
// updating the second and third minimum elements
else if (arr[i] < sMin) {
tMin = sMin;
sMin = arr[i];
}
else if (arr[i] < tMin) {
tMin = arr[i];
}
}
// print statement
System.out.println(“The Triplet with the smallest sum is: {“+ fMin + “, ” + sMin + “, ” + tMin + “}”);
}
// main method
public static void main(String[] args) {
int[] arr = {5, 1, -3, -4, -2, 6};
findSmallestTripletSum(arr);
}
}

Compile and Run

Output:

The Triplet with the smallest sum is: {-4, -3, -2}

Complexity Analysis

The time complexity of this approach is O(n) since we are only using one loop in the program.

The space complexity is O(1), as we are not using any extra space that grows with the input size.

26. Java program to increment all elements of an array by one.

The input array is defined as {1, 2, 3, 4, 5}. The method incrementArrayElements(int[] array) accepts an array as an argument. It then uses a for loop to iterate over each element in the array. Increment Operation: Inside the loop, the code array[i]++ increments each element by one. The final output is printed in the main() method, where the incremented array elements are displayed.

Example

public class Main {
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5};
incrementArrayElements(array);
// Print the incremented array
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + ” “);
}
}
public static void incrementArrayElements(int[] array) {
for (int i = 0; i < array.length; i++) {
array[i]++;
}
}
}

Compile and Run

Output:

2 3 4 5 6

27. Java program to move all zeroes to the end of the array.

For this approach, we traverse the array twice. In the first traversal, we do the following:

Iterate through the array while counting non-zero elements. Initialize the count at 0, which also indicates the position for the next non-zero element in the array.
For each non-zero element, position it at arr[count] and then increase the count by 1.
Once all elements have been processed, all non-zero entries will be moved to the front, keeping their original sequence.

In the second traversal, we do the following:

Following the initial traversal, all non-zero elements will occupy the beginning of the array, while the variable ‘count’ will indicate the position for the first zero.
Proceed from ‘count’ to the end of the array, filling all subsequent indices with 0.

Example

public class Main {
public static void main(String[] args) {
int[] arr = {1, 0, 2, 0, 3, 0, 4, 0};
int n = arr.length; //finding array length
int count = 0;
for (int i = 0; i < n; i++) { //loop iterate over the array
if (arr[i] != 0) { //compare if the array element is equals to zero or not
arr[count++] = arr[i]; //
}
}
while (count < n) {
arr[count++] = 0;
}
System.out.println(“Array after moving zeroes: ” + java.util.Arrays.toString(arr));
}
}

Compile and Run

Output:

Array after moving zeroes: [1, 2, 3, 4, 0, 0, 0, 0]

28. Reverse an array without changing the position of zeroes.

To solve the problem, the method involves moving through the array from both ends and swapping non-zero elements until reaching the centre. Throughout this procedure, the positions of zeroes are left intact. The code employs a while loop to bypass zeroes while decrementing the index from the end. When a non-zero element is detected, it gets swapped with the corresponding non-zero element from the opposite end. This swapping continues until the centre of the array is reached.

Example

import java.util.Arrays;
public class Main {
// Print function
public static void printReverse(int[] arr) {
// Print the original array
System.out.print(“Original array: “);
System.out.println(Arrays.toString(arr));
// Reverse the array without changing the position of zeroes
// Initialize the index to the last element
int j = arr.length – 1;
for (int i = 0; i < j; i++) {
// If the current element is zero, skip to the next element
if (arr[i] == 0) {
continue;
}
// If the current element is zero from the end
while (j > i && arr[j] == 0) {
// Decrement the index to the previous element
j–;
}
// Swap the elements
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// Decrement the index to the previous element
j–;
}
// Prints the reversed array
System.out.print(“Reversed array: “);
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
int[] arr = { 6, 0, 8, 0, 2, 0, 1 };
printReverse(arr);
}
}

Compile and Run

Output:

Original array: [6, 0, 8, 0, 2, 0, 1]
Reversed array: [1, 0, 2, 0, 8, 0, 6]

29. Java program to find the leader element in an array.

Given an array arr[] of size n, the task is to find all the Leaders in the array. An element is a Leader if it is greater than or equal to all the elements to its right side.

Note: The rightmost element is always a leader.

Example

public class Main {
public static void main(String[] args) {
int[] arr = {12, 11, 4, 7, 9, 6, 8, 15};
int n = arr.length;
int maxFromRight = arr[n – 1];
System.out.print(“Leader is: ” + maxFromRight + ” “);
for (int i = n – 2; i >= 0; i–) {
if (arr[i] > maxFromRight) {
maxFromRight = arr[i];
System.out.print(maxFromRight + ” “);
}
}
}
}

Compile and Run

Output:

Leader is: 15

30. Java program to find all the non-empty subarrays.

To create a subarray, we first need a starting index from the original array. We can choose this starting index by looping through the range [0 to n-1] and treating each index i as a potential starting point. For each selected starting index i, we then determine an ending index from the range [i to n-1]. A nested loop, running from [i to n-1], will assist in selecting the ending index. Once both the starting and ending indices are established, an innermost loop will be required to print the elements of the subarray.

Example

import java.util.ArrayList;
public class Main {
//Prints all subarrays in arr[0..n-1]
static void findSubArray(ArrayList<Integer> arr) {
int n = arr.size();
// Pick starting point
for (int i = 0; i < n; i++) {
// Pick ending point
for (int j = i; j < n; j++) {
// Print subarray between current starting and ending points
for (int k = i; k <= j; k++) {
System.out.print(arr.get(k) + ” “);
}
System.out.println();
}
}
}
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<>();
arr.add(1);
arr.add(2);
arr.add(3);
System.out.println(“Subarrays are:”);
findSubArray(arr);
}
}

Compile and Run

Output:

Subarrays are:
1
1 2
1 2 3
2
2 3
3

Array Programs in Java

1. Java program to find the sum of the array elements.

Example

2. Java program to find the reverse of an array.

Example

3. Java program to merge two arrays.

Example

4. Java program to find the second most significant element in a sorted matrix.

Example

5. Java program to find the k-th smallest element in a sorted matrix.

Example

6. Java program to remove duplicate elements from a sorted array.

Example

7. Java program to find the frequency of each word in a string array.

Example

8. Java program to find the missing number in a sorted array of consecutive integers.

Example

9. Java program to find the element that appears only once in an array.

Example

10. Java program to check if an array is a palindrome.

Example

11. Java program to shuffle elements of an array.

Example

12. Java program to check if two matrices are orthogonal.

Example

13. Java program to find the maximum element in a two-dimensional array.

Example

14. Java program to find the sum of each diagonal in a matrix.

Example

15. Java program to find the element with the maximum frequency in an array.

Example

16. Java program to rotate a two-dimensional array clockwise.

Example

17. Java program to sort a two-dimensional array across columns.

Example

18. Java program to perform matrix exponentiation to compute Fibonacci numbers efficiently.

Example

19. Given an array of integers, rearrange the array such that all even numbers appear before all odd numbers.

Note: Maintaining the relative order is not relevant for this problem.

Example

20. Java program to find the smallest missing positive number in an unsorted array.

Example

21. Java program to find the intersection of two arrays.

Example

22. Java program to find the longest subarray with an equal number of 0s and 1s.

Example

23. Java program to find the maximum product of two integers in an array.

Example

24. Java program to find the smallest subarray length with a sum greater than a given value.

Example

25. Java program to find the triplet with the smallest sum in an array.

Example

26. Java program to increment all elements of an array by one.

Example

27. Java program to move all zeroes to the end of the array.

Example

28. Reverse an array without changing the position of zeroes.

Example

29. Java program to find the leader element in an array.

Note: The rightmost element is always a leader.

Example

30. Java program to find all the non-empty subarrays.

Example

Comments

Leave a Reply Cancel reply