Mastering Basic Array Operations in Java: A Guide to Medium-Level Problems (Part-2)
24 min readMay 14, 2024
“Arrays are one of the fundamental data structures in Java, and understanding how to work with them is a key skill for any Java developer. They are used in a wide variety of applications, from storing data for processing to forming the basis for other data structures like heaps and hash tables. In this blog post, we will explore some medium-level problems related to arrays. These problems are designed to help you understand the basic operations that can be performed on arrays, such as accessing elements, iterating over the array, and modifying elements. We will also discuss some common algorithms and techniques used in array manipulation, such as sorting and searching. By the end of this post, you should have a solid understanding of how to work with arrays in Java and be able to solve medium level array-related problems. So, whether you’re a beginner just starting out with Java, or an experienced developer looking to brush up on your array manipulation skills, this guide is for you. Let’s get started!”
Problem: Given an array Arr[] of integers, rearrange the numbers of the given array into the lexicographically next greater permutation of numbers.
package org.example.Array.Day10;
/**
* Initialize two variables i and j.
* Start from the second last element of the array and move backwards. For each element at index i, if the element is
* less than the next element (arr[i] < arr[i + 1]), break the loop. This step is to find the first pair (arr[i],
* arr[i + 1]) where arr[i] < arr[i + 1].
* If no such pair is found (i.e., i becomes -1), it means the array is the last permutation. So, reverse the entire
* array and return.
* Start from the last element of the array and move backwards. For each element at index j, if the element is
* greater than arr[i] (arr[j] > arr[i]), break the loop. This step is to find the first element from the end that is
* greater than arr[i].
* Swap the elements at indices i and j. This is because arr[j] is the next greater element than arr[i] and swapping
* them will make the sequence just larger than the current one.
* Reverse the subarray from index i + 1 to the end of the array. This is because the elements after i in the
* original array were in descending order, so reversing them will make them in ascending order, which is the
* smallest possible order for them. This ensures that the sequence is the next lexicographically greater permutation.
* The swap method is a helper method that swaps the elements at two given indices in the array, and the reverseArray
* method is a helper method that reverses the elements in the array between two given indices. This algorithm works
* by first finding the first pair of elements that are in decreasing order from the end, swapping the smaller
* element with the next greater element from the end, and then reversing the elements after the smaller element to
* make the sequence the smallest possible one that is greater than the original sequence. This ensures that the
* sequence is the next lexicographically greater permutation.
*
* Time Complexity : O(N)
* Space Complexity : O(1)
*/
public class FindNextLexicographicallyGreaterPermutation {
public static void main(String[] args) {
// Let's consider we have a 6 digit array with number 1 to 6 then the lexicographical permutation are as follow:
// 123456, 123465, 123546, 123564, 123645, 123654, 124356, 124365, 124536, 124563, 124635, 124653, 125346,
// 125364, 125436, 125463, 125634, 125643, 126345, 126354, 126435, 126453, 126534, 126543, 132456, 132465,
// 132546, 132564, 132645, 132654, ..
// Now the problem is if we have given a number like 126354 then we need to find the next one in the sequence
// like 126435
int[] arr = {1, 2, 6, 3, 5, 4};
findNextLexicographicalPermutation(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
private static void findNextLexicographicalPermutation(int[] arr) {
int i;
int j;
for (i = arr.length - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1]) {
break;
}
}
if (i == -1) {
reverseArray(arr, 0, arr.length - 1);
}
for (j = arr.length - 1; j > i; j--) {
if (arr[j] > arr[i]) {
break;
}
}
swap(arr, i, j);
reverseArray(arr, i + 1, arr.length - 1);
}
private static void reverseArray(int[] arr, int startIndex, int endIndex) {
while (startIndex < endIndex) {
swap(arr, startIndex, endIndex);
startIndex++;
endIndex--;
}
}
private static void swap(int[] arr, int start, int end) {
int temp = arr[end];
arr[end] = arr[start];
arr[start] = temp;
}
}
Output : 1 2 6 4 3 5 Problem: There’s an array ‘A’ of size ’N’ with an equal number of positive and negative elements. Without altering the relative order of positive and negative elements, you must return an array of alternately positive and negative values.
package org.example.Array.Day10;
import java.util.Arrays;
/**
* The provided Java code is rearranging an array so that positive and negative numbers alternate, with the first
* number being positive. It uses two different approaches: a brute force approach and an optimized approach. Here
* are the steps for each approach:
* <p>
* Brute Force Approach:
* Initialize two arrays arrPositives and arrNegatives to store the positive and negative numbers from the input
* array respectively. Also, initialize a finalArray to store the final rearranged array.
* Iterate over each element in the input array. For each element:
* If the element is positive, add it to arrPositives.
* If the element is negative, add it to arrNegatives.
* After all elements have been processed, iterate over the arrPositives and arrNegatives arrays. For each index i:
* Set the 2 * i-th element of finalArray to the i-th element of arrPositives.
* Set the (2 * i) + 1-th element of finalArray to the i-th element of arrNegatives.
* Return finalArray.
*
* Time Complexity : O(N)
* Space Complexity : O(N)
* <p>
* Optimized Approach:
* Initialize two counters positiveCounter and negativeCounter to 0 and 1 respectively. Also, initialize a finalArray
* to store the final rearranged array.
* Iterate over each element in the input array. For each element:
* If the element is positive, add it to finalArray at the index positiveCounter and increment positiveCounter by 2.
* If the element is negative, add it to finalArray at the index negativeCounter and increment negativeCounter by 2.
* Return finalArray.
* In both approaches, the assumption is that the array has an equal number of positive and negative numbers and that
* the first number should be positive.
*
* Time Complexity : O(N)
* Space Complexity : O(N)
*/
public class RearrangeArrayAsAlternatePositiveAndNegative {
public static void main(String[] args) {
// Assumption is that array has equal number of positives and negatives numbers and we need to start with
// positive number.
int[] arr = {1, 2, -3, -1, -2, 3};
int[] arr1 = rearrangeArrayByBruteForce(arr);
System.out.println(Arrays.toString(arr1));
int[] arr2 = rearrangeArrayByOptimizeMethod(arr);
System.out.println(Arrays.toString(arr2));
}
private static int[] rearrangeArrayByOptimizeMethod(int[] arr) {
int positiveCounter = 0;
int negativeCounter = 1;
int[] finalArray = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0) {
finalArray[positiveCounter] = arr[i];
positiveCounter += 2;
} else {
finalArray[negativeCounter] = arr[i];
negativeCounter += 2;
}
}
return finalArray;
}
private static int[] rearrangeArrayByBruteForce(int[] arr) {
int[] arrPositives = new int[arr.length / 2];
int[] arrNegatives = new int[arr.length / 2];
int[] finalArray = new int[arr.length];
int positiveCounter = 0;
int negativeCounter = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0) {
arrPositives[positiveCounter++] = arr[i];
} else {
arrNegatives[negativeCounter++] = arr[i];
}
}
for (int i = 0; i < arr.length / 2; i++) {
finalArray[2 * i] = arrPositives[i];
finalArray[2 * i + 1] = arrNegatives[i];
}
return finalArray;
}
}
Output : [1, -3, 2, -1, 3, -2]
[1, -3, 2, -1, 3, -2]Problem: Given an array, print all the elements which are leaders. A Leader is an element that is greater than all of the elements on its right side in the array.
package org.example.Array.Day11;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
/**
* findLeadersInArrayUsingBruteForce algorithm:
* Create an empty list leaders to store the leaders in the array.
* Iterate over each element in the array except the last one. For each element at index i:
* Assume the current element is a leader by setting a boolean variable isLeader to true.
* Iterate over each element in the array from index i + 1 to the end. If any of these elements is greater than or
* equal to the current element, set isLeader to false and break the loop. This is because a leader is an element
* that is greater than all the elements to its right.
* If isLeader is true after the inner loop, add the current element to leaders.
* Add the last element of the array to leaders because it is always a leader.
* Sort leaders and return it.
*
* Time Complexity : O(N^2)
* Space Complexity : O(N)
*
* findLeadersInArrayUsingOptimalMethod algorithm:
* Create an empty list leaders to store the leaders in the array.
* Initialize a variable max to Integer.MIN_VALUE. This will hold the maximum element found so far from the right.
* Iterate over each element in the array from right to left. For each element at index i:
* If the element is greater than max, update max to the current element and add it to leaders. This is because a
* leader is an element that is greater than all the elements to its right.
* Sort leaders and return it.
* The findLeadersInArrayUsingBruteForce algorithm works by checking for each element if it is greater than all the
* elements to its right, which requires two nested loops and results in a time complexity of O(n^2). The
* findLeadersInArrayUsingOptimalMethod algorithm improves on this by iterating from right to left and keeping track
* of the maximum element found so far, which requires only one loop and results in a time complexity of O(n). Both
* algorithms then sort the leaders, which takes O(n log n) time.
*
* Time Complexity : O(N LOG N)
* Space Complexity : O(N)
*/
public class LeadersInAnArray {
public static void main(String[] args) {
int[] arr = {10, 22, 12, 3, 0, 6};
List<Integer> leadersInArrayUsingBruteForce = findLeadersInArrayUsingBruteForce(arr);
List<Integer> leadersInArrayUsingOptimalMethod = findLeadersInArrayUsingOptimalMethod(arr);
System.out.println(leadersInArrayUsingBruteForce);
System.out.println(leadersInArrayUsingOptimalMethod);
}
private static List<Integer> findLeadersInArrayUsingOptimalMethod(int[] arr) {
List<Integer> leaders = new ArrayList<>();
int max = Integer.MIN_VALUE;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] > max) {
max = arr[i];
leaders.add(arr[i]);
}
}
return leaders.stream().sorted().collect(Collectors.toList());
}
private static List<Integer> findLeadersInArrayUsingBruteForce(int[] arr) {
List<Integer> leaders = new ArrayList<>();
for (int i = 0; i < arr.length - 1; i++) {
boolean isLeader = true;
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] <= arr[j]) {
isLeader = false;
break;
}
}
if (isLeader) {
leaders.add(arr[i]);
}
}
leaders.add(arr[arr.length - 1]);
return leaders.stream().sorted().collect(Collectors.toList());
}
}
Output : [6, 12, 22]
[6, 12, 22]Problem: Given an array of integers and an integer k, return the total number of subarrays whose sum equals k.
package org.example.Array.Day12;
import java.util.HashMap;
import java.util.Map;
/**
* Initialize a HashMap called map to store the prefix sums and their counts. The key is the prefix sum and the value
* is the count of that prefix sum.
* Initialize a variable prefix_sum to 0. This will hold the sum of the elements of the array up to the current index.
* Initialize a variable count to 0. This will hold the count of subarrays with the given sum k.
* Iterate over the array from the first element to the last.
* For each element, add it to prefix_sum.
* If prefix_sum is equal to k, increment count by 1. This is because a subarray starting from the first element to
* the current index has a sum equal to k.
* If map contains a key equal to prefix_sum - k, increment count by the value of that key. This is because there are
* subarrays ending at the current index with sum equal to k.
* Add prefix_sum to map. If prefix_sum already exists in map, increment its value by 1. If not, add it with a value
* of 1.
* After the loop ends, return count which is the total number of subarrays with sum equal to k.
*
* Time Complexity : O(N)
* Space Complexity : O(N)
*/
public class CountSubArraysWithGivenSum {
public static void main(String[] args) {
int[] arr = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int k = 0;
int count = countSubArraysWithGivenSum(arr, k);
System.out.println(count);
}
private static int countSubArraysWithGivenSum(int[] arr, int k) {
Map<Long, Integer> map = new HashMap<>();
long prefix_sum = 0;
int count = 0;
int n = arr.length;
for (int i = 0; i < n; i++) {
prefix_sum = prefix_sum + arr[i];
if (prefix_sum == k) {
count++;
}
if (map.containsKey(prefix_sum - k)) {
count = count + map.get(prefix_sum - k);
}
map.put(prefix_sum, map.getOrDefault(prefix_sum, 0) + 1);
}
return count;
}
}
Output : 55Problem: You are given an array of ’N’ integers. You need to find the length of the longest sequence which contains the consecutive elements using Brute Force Approach.
package org.example.Array.Day12;
/**
* Check if the input array givenArray is empty. If it is, return 0 because there are no elements, hence no sequence.
* Initialize a variable longestLength to Integer.MIN_VALUE. This will hold the length of the longest consecutive
* sequence found so far.
* Iterate over each element in the array. For each element at index i:
* Initialize a variable localCounter to 1. This will hold the length of the consecutive sequence starting at the
* current element.
* Initialize a variable x to 1. This will be used to check for the next consecutive element.
* Enter a while loop that continues as long as the next consecutive element (current element + x) is found in the
* array. This is done by calling the searchNextConsecutiveElement method. Inside the while loop:
* Increment localCounter by 1 because a consecutive element has been found.
* Increment x by 1 to check for the next consecutive element.
* After the while loop, update longestLength to be the maximum of longestLength and localCounter. This is because we
* have found a new consecutive sequence and we want to keep track of the longest one.
* After the for loop, return longestLength which is the length of the longest consecutive sequence in the array.
*
* Time Complexity : O(N^3)
* Space Complexity : O(1)
*/
public class LongestConsecutiveSequenceInAnArrayUsingBruteForce {
public static void main(String[] args) {
int[] givenArray = {100, 200, 1, 3, 2, 4};
int longestSeqLength = LongestConsecutiveSeqUsingBruteForce(givenArray);
System.out.println(longestSeqLength);
}
private static int LongestConsecutiveSeqUsingBruteForce(int[] givenArray) {
if (givenArray.length == 0) {
return 0;
}
int longestLength = Integer.MIN_VALUE;
for (int i = 0; i < givenArray.length; i++) {
int localCounter = 1;
int x = 1;
while (searchNextConsecutiveElement(givenArray, givenArray[i] + x)) {
localCounter += 1;
x += 1;
}
longestLength = Math.max(longestLength, localCounter);
}
return longestLength;
}
private static boolean searchNextConsecutiveElement(int[] arr, int i) {
for (int j = 0; j < arr.length; j++) {
if (arr[j] == i) {
return true;
}
}
return false;
}
}
Output : 4Problem: You are given an array of ’N’ integers. You need to find the length of the longest sequence which contains the consecutive elements using Set Based Approach.
package org.example.Array.Day12;
import java.util.HashSet;
import java.util.Set;
/**
* Check if the input array givenArray is empty. If it is, return 0 because there are no elements, hence no sequence.
* Initialize a variable longest to 1. This will hold the length of the longest consecutive sequence found so far.
* Create a HashSet called set and add all elements from the array to it. This is done by iterating over each element
* in the array and adding it to the set. The set is used to allow for efficient lookups of elements.
* Iterate over each element i in the set:
* If the set does not contain i - 1, it means i could be the start of a new sequence. So, start a while loop that
* continues as long as the set contains i + x, where x starts from 1 and is incremented by 1 in each iteration. This
* is done to check for the next consecutive element in the sequence.
* Inside the while loop, increment a counter count by 1 for each consecutive element found. This counter keeps track
* of the length of the current sequence.
* After the while loop, update longest to be the maximum of longest and count. This is because we have found a new
* consecutive sequence and we want to keep track of the longest one.
* After the for loop, return longest which is the length of the longest consecutive sequence in the array.
* This algorithm works by using a set to efficiently check if an element is the start of a new sequence and to find
* the next consecutive element. It finds the longest consecutive sequence by checking each possible sequence
* starting from each element in the set.
*
* Time Complexity : O(N)
* Space Complexity : O(N)
*/
public class LongestConsecutiveSequenceInAnArrayUsingSet {
public static void main(String[] args) {
int[] givenArray = {100, 200, 1, 3, 2, 4};
int longestSeqLength = LongestConsecutiveSeqUsingSet(givenArray);
System.out.println(longestSeqLength);
}
private static int LongestConsecutiveSeqUsingSet(int[] givenArray) {
if (givenArray.length == 0) {
return 0;
}
int longest = 1;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < givenArray.length; i++) {
set.add(givenArray[i]);
}
for (Integer i : set) {
if (!set.contains(i - 1)) {
int x = 1;
int count = 1;
while (set.contains(i + x)) {
count = count + 1;
x = x + 1;
}
longest = Math.max(longest, count);
}
}
return longest;
}
}
Output : 4Problem: You are given an array of ’N’ integers. You need to find the length of the longest sequence which contains the consecutive elements using Optimal Approach.
package org.example.Array.Day12;
import java.util.Arrays;
/**
* Check if the input array givenArray is empty. If it is, return 0 because there are no elements, hence no sequence.
* Initialize a variable lastSmaller to Integer.MIN_VALUE. This will hold the value of the last smaller element found
* in the array.
* Initialize a variable counter to 0. This will hold the count of consecutive elements found so far.
* Initialize a variable longest to 1. This will hold the length of the longest consecutive sequence found so far.
* Iterate over each element in the array. For each element at index i:
* If the element is one greater than lastSmaller, increment counter by 1 and update lastSmaller to the current
* element. This is because a new consecutive element has been found.
* If the element is not equal to lastSmaller, update lastSmaller to the current element and reset counter to 1. This
* is because a new sequence has started.
* Update longest to be the maximum of longest and counter. This is because we have found a new consecutive sequence
* and we want to keep track of the longest one.
* After the for loop, return longest which is the length of the longest consecutive sequence in the array.
* This algorithm works by first sorting the array and then iterating over it to find the longest consecutive
* sequence. It uses the lastSmaller variable to keep track of the last smaller element and the counter variable to
* count the length of the current sequence. It updates longest whenever it finds a longer sequence.
*
* Time Complexity : O(N LOG N)
* Space Complexity : O(N)
*/
public class LongestConsecutiveSequenceInAnArrayUsingSorting {
public static void main(String[] args) {
int[] givenArray = {1, 2, 0, 1};
int[] ints = Arrays.stream(givenArray).sorted().toArray();
int longestSeqLength = LongestConsecutiveSeqUsingBetterWay(ints);
System.out.println(longestSeqLength);
}
private static int LongestConsecutiveSeqUsingBetterWay(int[] givenArray) {
int lastSmaller = Integer.MIN_VALUE;
int counter = 0;
int longest = 1;
if (givenArray.length == 0) {
return 0;
}
for (int i = 0; i < givenArray.length; i++) {
if (givenArray[i] - 1 == lastSmaller) {
counter += 1;
lastSmaller = givenArray[i];
} else if (givenArray[i] != lastSmaller) {
lastSmaller = givenArray[i];
counter = 1;
}
longest = Math.max(longest, counter);
}
return longest;
}
}
Output : 3Problem: Given a matrix if an element in the matrix is 0 then you will have to set its entire column and row to 0 and then return the matrix.
package org.example.Array.Day13;
/**
* Get the number of rows and columns of the input matrix and store them in variables row and column respectively.
* Iterate over each element in the matrix. For each element at position (i, j):
* If the element is 0, call the makeRowZero and makeColumnZero methods to set all elements in the same row and
* column to -1, unless they are already 0.
* After the double for loop, iterate over each element in the matrix again. For each element at position (i, j):
* If the element is -1, set it to 0.
* Print the matrix.
* The makeRowZero method sets all elements in a given row to -1, unless they are already 0. It does this by
* iterating over each element in the row and checking if it's not 0 before setting it to -1. The makeColumnZero
* method sets all elements in a given column to -1, unless they are already 0. It does this by iterating over each
* element in the column and checking if it's not 0 before setting it to -1. This algorithm works by first marking
* the rows and columns that need to be set to 0 by setting their elements to -1, and then setting these elements to
* 0 in a second pass. The use of -1 is to avoid setting elements to 0 prematurely which would cause other elements
* to be set to 0 incorrectly.
*
* Time Complexity : O((N*M)*(N+M))
* Space Complexity : O(1)
*/
public class SetMatrixZeroUsingBruteForce {
public static void main(String[] args) {
int[][] matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
setMatrixZeroUsingBruteForce(matrix);
}
private static void setMatrixZeroUsingBruteForce(int[][] matrix) {
int row = matrix.length;
int column = matrix[0].length;
System.out.println("no of rows are " + row + "no of columns are " + column);
for (int i = 0; i <= row - 1; i++) {
for (int j = 0; j <= column - 1; j++) {
if (matrix[i][j] == 0) {
makeRowZero(matrix, column, i);
makeColumnZero(matrix, row, j);
}
}
}
for (int i = 0; i <= row - 1; i++) {
for (int j = 0; j <= column - 1; j++) {
if (matrix[i][j] == -1) {
matrix[i][j] = 0;
}
}
}
System.out.println(matrix.toString());
}
private static void makeRowZero(int[][] matrix, int column, int i) {
for (int j = 0; j <= column - 1; j++) {
if (matrix[i][j] != 0) {
matrix[i][j] = -1;
}
}
}
private static void makeColumnZero(int[][] matrix, int row, int j) {
for (int i = 0; i <= row - 1; i++) {
if (matrix[i][j] != 0) {
matrix[i][j] = -1;
}
}
}
}
Output : 1
0
1
0
0
0
1
0
1package org.example.Array.Day13;
/**
* Get the number of rows and columns of the input matrix and store them in variables row and column respectively.
* Create two integer arrays rowIndex and columnIndex of size row and column respectively. These arrays will be used
* to mark the rows and columns that contain a 0.
* Iterate over each element in the matrix. For each element at position (i, j):
* If the element is 0, set rowIndex[i] and columnIndex[j] to 1. This marks the row and column that contain a 0.
* After the double for loop, iterate over each element in the matrix again. For each element at position (i, j):
* If rowIndex[i] or columnIndex[j] is 1, set the element to 0. This sets all elements in a row or column to 0 if
* that row or column contains a 0.
* Print the matrix.
* This algorithm works by first marking the rows and columns that contain a 0, and then setting all elements in
* those rows and columns to 0. The use of the rowIndex and columnIndex arrays allows us to do this in a more
* efficient way than the brute force approach, which would require a separate pass over the matrix for each 0 found.
*
* Time Complexity : O(N*M)
* Space Complexity : O(N+M)
*/
public class SetMatrixZeroUsingBetterApproach {
public static void main(String[] args) {
int[][] matrix = {{0,1,2,0},{3,4,5,2},{1,3,1,5}};
setMatrixZeroUsingBetterApproach(matrix);
}
private static void setMatrixZeroUsingBetterApproach(int[][] matrix) {
int row = matrix.length;
int column = matrix[0].length;
System.out.println("no of rows are " + row + "no of columns are " + column);
int[] rowIndex = new int[row];
int[] columnIndex = new int[column];
for (int i = 0; i <= row - 1; i++) {
for (int j = 0; j <= column - 1; j++) {
if(matrix[i][j] == 0) {
rowIndex[i] = 1;
columnIndex[j] = 1;
}
}
}
for (int i = 0; i <= row - 1; i++) {
for (int j = 0; j <= column - 1; j++) {
if(rowIndex[i] == 1 || columnIndex[j] == 1) {
matrix[i][j] = 0;
}
}
}
System.out.println(matrix);
}
}
Output : 0
0
0
0
0
4
5
0
0
3
1
0package org.example.Array.Day13;
/**
* Get the number of rows and columns of the input matrix and store them in variables row and column respectively.
* Initialize a variable col0 to 1. This will be used to track if the first column contains a 0.
* Iterate over each element in the matrix. For each element at position (i, j):
* If the element is 0, set the first element of the ith row and the jth column to 0. This marks the row and column
* that contain a 0.
* If j is 0, set col0 to 0. This is because the first column contains a 0.
* After the double for loop, iterate over the matrix again starting from the second row and the second column. For
* each element at position (i, j):
* If the first element of the ith row or the jth column is 0, set the element to 0. This sets all elements in a row
* or column to 0 if that row or column contains a 0.
* If the first element of the matrix is 0, set all elements in the first row to 0.
* If col0 is 0, set all elements in the first column to 0.
* This algorithm works by first marking the rows and columns that contain a 0, and then setting all elements in
* those rows and columns to 0. The first element of each row and column is used to mark that row or column. The col0
* variable is used to mark the first column because the first element of the matrix is also used to mark the first row.
*
* Time Complexity : O(N*M)
* Space Complexity : O(1)
*/
public class SetMatrixZeroUsingOptimal {
public static void main(String[] args) {
int[][] matrix = {
{1, 1, 1},
{1, 0, 1},
{1, 1, 1}
};
setMatrixZeroUsingOptimalApproach(matrix);
}
private static void setMatrixZeroUsingOptimalApproach(int[][] matrix) {
int row = matrix.length;
int column = matrix[0].length;
int col0 = 1;
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
// if we encounter a 0
if(matrix[i][j] == 0) {
// the first element of ith row hold that state
matrix[i][0] = 0;
if(j != 0) {
// the first element of jth column hold that state except for first column
matrix[0][j] = 0;
}
else {
// for first column
col0 = 0;
}
}
}
}
// Mark with 0 from (1,1) to (row-1 and column-1):
for (int i = 1; i < row; i++) {
for (int j = 1; j < column; j++) {
if(matrix[i][j] != 0) {
if(matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
}
if(matrix[0][0] == 0) {
for (int j = 0; j < column; j++) {
matrix[0][j] = 0;
}
}
if(col0 == 0) {
for (int i = 0; i < row; i++) {
matrix[i][0] = 0;
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.println(matrix[i][j]);
}
}
}
}
Output : 1
0
1
0
0
0
1
0
1Problem: Given a matrix, your task is to rotate the matrix 90 degrees clockwise.
package org.example.Array.Day14;
/**
* Get the length of the input matrix and store it in a variable n. This represents the number of rows (or columns)
* in the matrix.
* Create a new 2D array rotatedMatrix of size n x n. This will hold the rotated matrix.
* Iterate over each element in the input matrix. For each element at position (i, j):
* Calculate the new position for this element in the rotated matrix. The new position is (j, n-i-1).
* Assign the value of the element at position (i, j) in the input matrix to the new position in rotatedMatrix.
* After the double for loop, return rotatedMatrix which is the input matrix rotated by 90 degrees.
* This algorithm works by calculating the new position of each element in the rotated matrix. The new position is
* determined by the rule (i, j) -> (j, n-i-1), where (i, j) is the position of an element in the original matrix and
* (j, n-i-1) is its position in the rotated matrix.
*
* Time Complexity : O(N*M)
* Space Complexity : O(N*M)
*/
public class RotateMatrixBy90UsingBruteForce {
public static void main(String[] args) {
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int[][] ints = rotateByBruteForce(matrix);
for (int i = 0; i < ints.length; i++) {
for (int j = 0; j < ints.length; j++) {
System.out.print(ints[i][j] + " ");
}
}
}
private static int[][] rotateByBruteForce(int[][] matrix) {
int n = matrix.length;
int[][] rotatedMatrix = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rotatedMatrix[j][n-i-1] = matrix[i][j];
}
}
return rotatedMatrix;
}
}
Output : 7 4 1 8 5 2 9 6 3 package org.example.Array.Day14;
/**
* Get the number of rows and columns of the input matrix and store them in variables rows and columns respectively.
* Perform a transpose operation on the matrix. This is done by swapping elements at position (i, j) with elements at
* position (j, i). This is done for all elements above the main diagonal (where i < j). The transpose of a matrix is
* obtained by flipping it over its main diagonal.
* Iterate over each row i of the matrix.
* For each row, iterate over each column j starting from i.
* Swap the element at position (i, j) with the element at position (j, i).
* Reverse each row of the transposed matrix. This is done by swapping elements at position (i, j) with elements at
* position (i, columns - 1 - j). This is done for the first half of each row (where j < columns / 2).
* Iterate over each row i of the matrix.
* For each row, iterate over each column j up to columns / 2.
* Swap the element at position (i, j) with the element at position (i, columns - 1 - j).
* After the two for loops, return the matrix which is now rotated by 90 degrees.
* This algorithm works by first transposing the matrix and then reversing each row. The transpose operation makes
* the rows of the original matrix to become columns in the transposed matrix. The reverse operation then adjusts the
* order of the elements in each row to achieve the rotation effect.
*
* Time Complexity : O(N*M)
* Space Complexity : O(N*M)
*/
public class RotateMatrixBy90UsingTranspose {
public static void main(String[] args) {
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int[][] ints = rotateByTranspose(matrix);
for (int i = 0; i < ints.length; i++) {
for (int j = 0; j < ints.length; j++) {
System.out.print(ints[i][j] + " ");
}
}
}
private static int[][] rotateByTranspose(int[][] matrix) {
int rows = matrix.length;
int columns = matrix[0].length;
for (int i = 0; i < rows; i++) {
for (int j = i; j < columns; j++) {
int temp = 0;
temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns / 2; j++) {
int temp = 0;
temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length - 1 - j];
matrix[i][matrix.length - 1 - j] = temp;
}
}
return matrix;
}
}
Output : 7 4 1 8 5 2 9 6 3 Problem: Given a Matrix, print the given matrix in spiral order.
package org.example.Array.Day14;
import java.util.ArrayList;
import java.util.List;
/**
* Create an empty list ans to store the elements of the matrix in spiral order.
* Get the number of rows and columns of the input matrix and store them in variables rows and columns respectively.
* Initialize four pointers top, bottom, left, and right to 0, rows - 1, 0, and columns - 1 respectively. These
* pointers represent the boundaries of the current layer of the matrix that we are traversing.
* Start a while loop that continues as long as top is less than or equal to bottom and left is less than or equal to
* right. This ensures that we stop when we have traversed all layers of the matrix.
* Traverse from left to right along the top row, from column left to right, and add each element to ans. Then
* increment top to move to the next row.
* Traverse from top to bottom along the right column, from row top to bottom, and add each element to ans. Then
* decrement right to move to the previous column.
* Check if top is less than or equal to bottom to ensure there are rows remaining. If so, traverse from right to
* left along the bottom row, from column right to left, and add each element to ans. Then decrement bottom to move
* to the previous row.
* Check if left is less than or equal to right to ensure there are columns remaining. If so, traverse from bottom to
* top along the left column, from row bottom to top, and add each element to ans. Then increment left to move to the
* next column.
* After the while loop, return ans which contains the elements of the matrix in spiral order.
* This algorithm works by traversing the matrix layer by layer, starting from the outermost layer and moving towards
* the innermost layer. In each layer, it traverses the top row from left to right, the right column from top to
* bottom, the bottom row from right to left, and the left column from bottom to top, in that order.
*
* Time Complexity : O(N*M)
* Space Complexity : O(N*M)
*/
public class SpiralTraversalOfMatrix {
public static void main(String[] args) {
// //Matrix initialization
int[][] matrix = {{1, 2, 3, 5},
{4, 5, 6, 6},
{7, 8, 9, 9}};
List<Integer> integers = spiralTraversalOfMatrix(matrix);
System.out.println(integers);
}
private static List<Integer> spiralTraversalOfMatrix(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int rows = matrix.length;
int columns = matrix[0].length;
// Initialize the pointers required for traversal
int top = 0;
int bottom = rows - 1;
int left = 0;
int right = columns - 1;
// Loop until all elements are not traversed
while (top <= bottom && left <= right) {
// moving left to right
for (int i = left; i <= right; i++) {
ans.add(matrix[top][i]);
}
top++;
// moving top to bottom
for (int i = top; i <= bottom; i++) {
ans.add(matrix[i][right]);
}
right--;
// moving right to left
if (top <= bottom) {
for (int i = right; i >= left; i--) {
ans.add(matrix[bottom][i]);
}
bottom--;
}
// moving bottom to top
if (left <= right) {
for (int i = bottom; i >= top; i--) {
ans.add(matrix[i][left]);
}
left++;
}
}
return ans;
}
}
Output : [1, 2, 3, 5, 6, 9, 9, 8, 7, 4, 5, 6]For other medium level problems, see my article
