In Java, an array represents a sequential data structure that contains elements of the same data type stored in adjacent memory locations. In the upcoming section, we will explore a range of array-related programs covering operations, manipulation, sorting, searching, and more.
1. Java program to find the sum of the array elements.
In order to calculate the total of the elements in the array, the initial step involves creating and initializing an array. Subsequently, a method named sum is established to sum up the array elements. Within this method, a loop is utilized to iterate through each element of the array and incrementally add each element to the sum variable. The sum method is then invoked in the main method to obtain the sum of the elements in the array.
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());
}
}
Output:
The sum of the given array is: 69
2. Java program to find the reverse of an array.
To reverse an array, we reverse the order of its elements by starting from the last element and going to the first. Initially, we set up an array. Then, a loop is used to go through the array until it is fully reversed. During each iteration, we exchange the first element with the last one, the second element with the second-to-last one, and so forth. Finally, we transform the array into a string and display 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));
}
}
Output:
[5, 4, 3, 2, 1]
3. Java program to merge two arrays.
In this particular program, we have implemented a custom approach to combine two arrays, offering a distinct alternative to the built-in methods available. This technique grants us complete authority over the merging operation by directly integrating the arrays. This can be beneficial in scenarios where a more tailored merging process is required.
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));
}
}
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.
Within a matrix that is sorted, the elements within the rows and columns are organized in an ascending manner. By systematically traversing the matrix, we can identify both the largest and second-largest elements, thus deducing the second-largest element. This process involves recording the second-largest element as we move through the entire matrix.
The software employs a straightforward method to identify the second-highest element within an ordered matrix. It utilizes a nested iteration to navigate through the matrix in reverse sequence, evaluating each element against the current largest and second-largest elements. The application dynamically adjusts the variables representing the largest and second-largest elements. Upon completion, it displays 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);
}
}
Output:
Second largest element in the sorted matrix is: 8
Complexity Analysis
The time complexity of the algorithm is denoted as O(rows * cols), where rows and cols represent the respective dimensions of the matrix being processed.
The space complexity is O(1) because only a fixed amount of extra space is utilized.
5. Java program to find the k-th smallest element in a sorted matrix.
In a matrix sorted in ascending order both horizontally and vertically, the objective is to determine the kth smallest item in the matrix.
The software utilizes a minimum heap created with a PriorityQueue to determine the kth smallest item in a matrix that is already sorted. The method findKthSmallest starts by setting up the minHeap and inserting the items from the initial column. It proceeds with k-1 rounds, retrieving the smallest item, identifying its position, and including the subsequent item from the identical row to the minHeap. Ultimately, the function delivers the kth smallest item. The primary function demonstrates the method using a specified matrix and k parameter.
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);
}
}
Output:
The 4-th smallest element in the sorted matrix is: 6
Complexity Analysis
Time Complexity Explanation: The time complexity for this algorithm is expressed as O(k * log(rows)), where k represents a constant factor.
Space Complexity: The memory required to store the elements in the min-heap is proportional to the number of rows and can be expressed as O(rows).
6. Java program to remove duplicate elements from a sorted array.
When dealing with a sorted array, it is common to encounter consecutive duplicate elements. To eliminate these duplicates from an ordered array without changing its order, we can perform an in-place modification ensuring that each distinct element appears only once. The Java solution involves a class named "RemoveDuplicates" that contains a method called "removeDuplicates." This method is responsible for removing duplicates and returning the updated length of the array without duplicates.
The process begins by checking if the array is empty and then setting the initial value of a variable named "nextUnique" to 1. The method iterates through the array starting from the second element. During each iteration, it identifies unique elements and assigns them to the position indicated by "nextUnique." Subsequently, it increments the "nextUnique" variable. Upon completion of the iteration, the value of "nextUnique" corresponds to the new length of the array without duplicates.
To demonstrate the functionality, the "main" function is utilized to showcase the "removeDuplicates" method by displaying the modified array after duplicate removal.
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]+" ");
}
}
}
Output:
Modified Array: 1 2 3 4 5
Complexity Analysis
The time complexity of the algorithm is represented as O(n), where n indicates the number of elements in the array.
The space complexity is O(1) because the array is altered directly without the need for extra data structures.
7. Java program to find the frequency of each word in a string array.
Let's determine the occurrence rate of individual words within an array of strings by utilizing a Java application. When presented with a collection of strings, our objective is to ascertain the frequency of each word's occurrence. This task is accomplished by leveraging a hash map within the program.
An uncomplicated method involves splitting each string into individual words and then storing the count of each word in a hash map. By creating an empty HashMap at the start, the code iterates over every string in the array. For each string, it checks if the word already exists in the HashMap.
Should the word already exist in the hash map, its frequency will be incremented; otherwise, it will be initialized to 1, and the word will be inserted into the hash map. Subsequently, the application will display the word-frequency pairs that have been stored in the HashMap. This method effectively monitors and tallies the occurrences of individual words, enabling precise analysis of word frequencies within the array of strings.
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());
}
}
}
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 computational complexity is denoted as O(n*m), with 'n' indicating the quantity of strings in the array and 'm' representing the highest occurring common phrase in each string.
The program's space complexity is represented as O(n), with 'n' denoting the overall quantity of words contained within the array.
8. Java program to find the missing number in a sorted array of consecutive integers.
Applying the binary search algorithm enables us to identify the absent integer within an ordered array of consecutive integers. Initially, we set the index of the first element as low and the rest as high. By calculating the anticipated value of the middle element, which equals the first element plus the middle index, we can determine whether the absent integer lies to the left or right of this element. This process iterates until only a single element remains in the search range, prompting us to adjust low or high accordingly. Ultimately, the absent number corresponds to the anticipated value at the low index.
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);
}
}
Output:
Missing number: 5
Complexity Analysis
Time Complexity: The time complexity of employing binary search is O(log n), where n represents the array's size.
Space Complexity: The software exhibits a space complexity of O(1), where only a limited number of variables are utilized to monitor the low, high, and mid indices, along with the anticipated value.
9. Java program to find the element that appears only once in an array.
A method commonly employed to identify the element that occurs exactly once in an array relies heavily on utilizing the XOR operation. This technique involves XORing all elements in the array, causing elements that occur multiple times to nullify each other and leaving only the element that occurs uniquely. To implement this strategy, we start by setting a variable 'unique' to zero. Subsequently, we traverse through each element in the array, performing XOR with the 'unique' variable and updating the result back into 'unique.' Upon completing the iteration, the 'unique' variable will contain the value of the element 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);
}
}
Output:
The element that appears only once: 4
Complexity Analysis
Algorithm Efficiency: The time complexity associated with this method is O(n), with 'n' representing the size of the array.
Space Analysis: The space complexity is denoted as O(1) due to the utilization of only one variable to store the output.
10. Java program to check if an array is a palindrome.
In order to determine if an array is a palindrome, we can employ a two-pointer technique where one pointer begins at the beginning of the array and the other at the end. The elements at these pointers are compared iteratively, gradually moving them towards each other until they converge at the center. If, at any stage, the elements at the pointers do not match, we can ascertain that the array is not a palindrome. Conversely, if the pointers traverse the entire array without encountering any unequal elements, then the array qualifies as a palindrome. This dual-pointer strategy enables us to efficiently validate palindromes without requiring extra storage 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.");
}
}
}
Output:
The array is a palindrome.
Complexity Analysis
The time complexity of the method described above is O(n), with n representing the size of the array.
The space complexity remains constant at O(1) since there is no additional space being utilized.
11. Java program to shuffle elements of an array.
A widely employed method for rearranging the elements of an array is the Fisher-Yates shuffle algorithm. This algorithm guarantees that every item in the array is rearranged in a random manner. The process commences by traversing the array in a reverse order, starting from the last element. During each iteration, the current element is included in the range of the unshuffled elements that are yet to be processed to generate a random index. Subsequently, the element at the current index is interchanged with the element at the randomly determined index. This swapping process persists until the first element is reached, resulting in an array where the elements are shuffled into a random sequence.
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 + " ");
}
}
}
Output:
Original array:
1 2 3 4 5
Shuffled array:
5 2 1 3 4
Complexity Analysis
The computational complexity of this method is represented as O(N), with N denoting the array's size.
The space complexity is O(1) as we utilize a constant amount of additional space for the random assortment.
12. Java program to check if two matrices are orthogonal.
In order to determine the orthogonality of two matrices, we need to compute the dot product of the matching rows or columns within the matrices. The matrices are considered orthogonal if the dot product equals 0 for every pair. The process involves iterating over the rows or columns, computing the dot product, and if any dot product is not 0, the algorithm returns false. Additionally, the algorithm verifies that the dimensions are suitable. If all dot products are indeed 0, the algorithm returns true, indicating 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.");
}
}
}
Output:
The matrices are not orthogonal.
Complexity Analysis:
The computational complexity of this method is represented as O(n), with n denoting the extent of rows or columns in the matrices.
The space complexity remains at O(1) due to the absence of any extra data structures being utilized.
13. Java program to find the maximum element in a two-dimensional array.
To find the highest element in a two-dimensional array, we first assign the variable 'max' with the minimum possible value based on the data type of the array elements. We then iterate through each row and column of the array individually. During each iteration, we compare every element with the current value of 'max' and update 'max' if the element is greater. After iterating through all elements, 'max' will hold the maximum element in the two-dimensional array. This approach allows us to efficiently identify the highest element by continuously comparing each element with the current maximum value.
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);
}
}
Output:
The maximum element in the array is: 9
Complexity Analysis
The computational complexity of this method is denoted as O(n * m), where n represents the total rows and m represents the total columns in the two-dimensional array.
The space complexity remains at O(1) because no additional space is utilized that scales with the input size.
14. Java program to find the sum of each diagonal in a matrix.
In order to determine the total of each diagonal in a matrix, we need to go through each element and determine the diagonal index by adding the row and column indices. Subsequently, we accumulate the value of the element to the appropriate diagonal total stored in an array. Once all elements have been processed, the array will hold the sum for 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);
}
}
}
Output:
Sum of each diagonal:
1
6
15
14
9
Complexity Analysis
The method has a time complexity of O(m*n), with m representing the total rows and n representing the total columns in the matrix.
The space complexity amounts to O(m + n) due to the necessity of storing the diagonal sums within an array.
15. Java program to find the element with the maximum frequency in an array.
A HashMap is employed to keep track of how often each item appears in the array to pinpoint the item that occurs most frequently. By iterating through the array and adjusting the frequency in the hashmap, we can determine the item with the highest frequency. By examining the frequency values stored in the HashMap, we can pinpoint the item with the maximum frequency. This method enables us to effectively identify the item 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));
}
}
Output:
Element with maximum frequency is: 3
Complexity Analysis
The time complexity associated with this method is denoted as O(n), with 'n' representing the array's size.
The spatial complexity is denoted as O(n) due to the fact that in the worst-case scenario, a HashMap can store a maximum of n distinct elements.
16. Java program to rotate a two-dimensional array clockwise.
In order to perform a clockwise rotation on a two-dimensional array, a two-step method can be applied: transposing the array and reversing each row. Initially, the array is traversed, and each element at position (i, j) is swapped with the element at position (j, i) to accomplish the transposition. Subsequently, by iterating through every row of the transposed array, the row is reversed by exchanging the elements from both ends of the row until they converge at the center. This sequence of operations effectively rotates the array in a clockwise direction.
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();
}
}
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 computational complexity of this method is denoted as O(n squared), with n representing the dimension of the array.
The space complexity remains at O(1) because the rotation is performed in situ without relying on extra storage mechanisms.
17. Java program to sort a two-dimensional array across columns.
A personalized comparator is created to compare rows by the specified column for sorting a two-dimensional array horizontally. The Arrays.sort function is utilized with the custom comparator passed as a parameter. The sorting process utilizes a comparator to assess rows based on the designated column and organize them appropriately. This technique allows for the efficient sorting of the two-dimensional array horizontally.
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();
}
}
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 computational complexity of this method is O(n log n), with n representing the quantity of rows present in the matrix.
The sorting process being carried out in situ ensures that the space complexity remains at O(1).
18. Java program to perform matrix exponentiation to compute Fibonacci numbers efficiently.
An alternative approach to representing the Fibonacci sequence is by utilizing a matrix and leveraging matrix multiplication for efficient computation of Fibonacci numbers through matrix exponentiation. This technique involves the creation of a transformation matrix that corresponds to the Fibonacci series, application of matrix multiplication and exponentiation techniques, and subsequently raising the matrix to the required power using the powerMatrix method. Through the removal of the Fibonacci number from the designated matrix, rapid computation of Fibonacci numbers can also be achieved.
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);
}
}
Output:
Fibonacci number at position 10 is: 55
Complexity Analysis
The computational efficiency of this method is characterized by a time complexity of O(log n) due to its utilization of the exponentiation by squaring method for matrix multiplication.
The space complexity is O(1) as it requires only a constant amount of space for a fixed-size matrix and a small number of extra 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.
An array can be rearranged such that all even numbers precede odd numbers using a two-pointer strategy. The right pointer starts from the end and moves backwards, while the left pointer progresses forward from the beginning. Each iteration involves evaluating the elements indicated by the pointers and performing necessary exchanges. At the end of the process, all even numbers will be positioned before odd numbers in the array.
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();
}
}
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
This method has a time complexity of O(n), with n representing the total count of items in the array.
The space complexity remains at O(1) due to the rearrangement being executed in situ without the utilization of extra data structures.
20. Java program to find the smallest missing positive number in an unsorted array.
To identify the smallest missing positive number in an unordered array, you can reorganize the array by mapping each positive integer to its correct index. This can be achieved by iterating through the array and swapping each element containing a positive integer with the element at the intended index. Subsequently, another iteration through the array is conducted to pinpoint the initial index where an element no longer aligns with the expected value post-rearrangement. This particular index signifies the smallest missing positive number in the array. In scenarios where all elements correspond to their expected values, the smallest missing positive number would be the subsequent positive integer following the array's 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);
}
}
Output:
Smallest Missing Positive Number: 2
Complexity Analysis
This method guarantees a time efficiency of O(n) and a space efficiency of O(1) by rearranging and searching within the original data structure without using extra memory.
21. Java program to find the intersection of two arrays.
Utilizing a HashSet data structure is an effective method for determining the intersection of two arrays. Initially, a HashSet is instantiated and populated with elements from one array. Subsequently, the algorithm iterates through the second array, verifying the presence of each element in the HashSet. Upon confirmation of existence, the element is appended to the resultant ArrayList, and subsequently eliminated from the HashSet to prevent redundancy.
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);
}
}
Output:
Intersection: [2]
Complexity Analysis
The algorithm's time complexity is represented as O(n), with n denoting the dimension of the larger array used in the process.
The space complexity is denoted as O(m), with m representing the HashSet's size.
22. Java program to find the longest subarray with an equal number of 0s and 1s.
By employing the prefix sum technique, we can identify the longest contiguous subarray that has an identical count of 0s and 1s. This is achieved by maintaining a cumulative sum as we iterate through the array, assigning a value of 1 for each 1 encountered and -1 for each 0. Once the cumulative sum reaches zero, it indicates an equal number of 0s and 1s encountered so far. To determine the longest subarray meeting this condition, we utilize a HashMap to store the cumulative sum along with its corresponding index. Whenever a previously seen cumulative sum reappears, we update the maximum length by subtracting the previously stored index from the current index. By consistently tracking the maximum length during the iteration process, we can successfully identify the longest subarray where the count of 0s and 1s are balanced.
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);
}
}
Output:
Length of the longest subarray with equal 0s and 1s: 6
Complexity Analysis
The time complexity of this method is O(n) because we traverse the array once.
The space complexity is O(n) because we are storing both the running total and its associated index in the HashMap.
23. Java program to find the maximum product of two integers in an array.
In order to determine the highest possible product of two integers within a given array, we can follow these steps:
- Begin by setting both ```
The sum of the given array is: 69
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));
}
}
- Next, iterate through the array and compare each element with ```
The sum of the given array is: 69
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));
}
}
The sum of the given array is: 69
- Upon completion of the iteration process, the maximum product can be calculated by multiplying ```
The sum of the given array is: 69
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));
}
}
The sum of the given array is: 69
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));
}
}
### 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);
}
}
Output:
Maximum Product: 20
Complexity Analysis
The computational complexity of this method is O(n), with n representing the array's size.
The space complexity is O(1) as it only requires a constant amount of additional space to save the highest and second highest elements.
### 24. Java program to find the smallest subarray length with a sum greater than a given value.
In order to determine the shortest length of a subarray whose sum surpasses a specified threshold, the sliding window method can be employed. This strategy revolves around managing a dynamic window that grows and shrinks as the sum is calculated. Initially, an empty window is established and is progressively enlarged by incorporating elements from the right side. Upon surpassing the target sum, the minimum subarray length is updated. Subsequently, the window is shrunk from the left side by removing elements until the sum is less than or equal to the specified threshold. This process continues iteratively until the entire array has been traversed.
### 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);
}
}
Output:
Smallest Subarray Length: 3
Complexity Analysis
The computational complexity of this method is represented as O(n), with n denoting the array's size.
The spatial complexity is O(1) as we solely require a fixed amount of additional space to store variables.
### 25. Java program to find the triplet with the smallest sum in an array.
Utilizing three variables or an integer array of size three, we can employ a loop to identify the minimum elements within the provided array. The objective is to identify the smallest sum, hence the focus on locating the minimum elements.
### 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);
}
}
Output:
The Triplet with the smallest sum is: {-4, -3, -2}
Complexity Analysis
The time complexity of this method is O(n) because it involves the utilization of a single loop within the code.
The space complexity remains at O(1) since there is no additional space being utilized that scales with the size of the input.
### 26. Java program to increment all elements of an array by one.
The array given for input is {1, 2, 3, 4, 5}. The function incrementArrayElements(int[] array) is designed to take an array as input. It utilizes a for loop to go through each element in the array. Incrementing Process: During each iteration, the statement array[i]++ increases the value of each element by one. The resulting updated array elements are then shown in the main() function when the program is executed.
### 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]++;
}
}
}
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.
During the second pass, the steps are as follows:
- After the initial pass, all elements that are not zero will be at the start of the array, and the 'count' variable will specify the placement of the first zero.
- Starting from the 'count' index, continue to the end of the array, replacing all following positions with zeros.
### 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));
}
}
Output:
Array after moving zeroes: [1, 2, 3, 4, 0, 0, 0, 0]
### 28. Reverse an array without changing the position of zeroes.
In order to address the issue, the approach requires traversing the array from both extremes and exchanging non-zero values until the midpoint is reached. Zero positions remain unchanged during this process. A while loop is used in the implementation to skip over zeros while decreasing the index from the end. Upon encountering a non-zero value, it is interchanged with the corresponding non-zero value from the opposite side. This exchange process persists until the midpoint of the array is attained.
### 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);
}
}
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.
In a scenario where an array arr[] of size n is provided, the objective is to identify all the Leaders within the array. A Leader is defined as an element that surpasses or equals all elements positioned to its right.
#### 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 + " ");
}
}
}
}
Output:
Leader is: 15
### 30. Java program to find all the non-empty subarrays.
In order to generate a subarray, the initial step involves identifying a starting point within the primary array. This starting index can be determined by iterating over the range [0 to n-1] and considering each index i as a potential starting position. Following the selection of a starting index i, the subsequent step is to identify an ending index within the range [i to n-1]. To accomplish this, a nested loop that runs from [i to n-1] will be utilized to pinpoint the ending index. Subsequently, after establishing both the starting and ending indices, an inner loop will be necessary to display the elements contained within 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);
}
}
Output:
Subarrays are:
1
1 2
1 2 3
2
2 3
3