Mastering Basic Array Operations in Java: A Guide to Medium-Level Problems (Part-1)
16 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: Check if a pair exists with given sum in an array
package org.example.Array.Day6;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* The provided Java code is checking if a pair of elements exists in an array that sums up to a given number. It
* uses three different approaches: a brute force approach, a HashMap-based approach, and a two-pointer approach.
* Here are the steps for each approach: Brute Force Approach:
* Two nested loops are used to generate all possible pairs of elements in the array.
* For each pair, it checks if the sum of the elements in the pair is equal to the given sum.
* If such a pair is found, it returns "YES". If no such pair is found after checking all pairs, it returns "NO".
*
* Time Complexity : O(N^2)
* Space Complexity : O(1)
*
* HashMap-Based Approach:
* A HashMap is created to store the elements of the array.
* A loop is used to iterate over each element in the array. For each element, it checks if the difference between
* the given sum and the element is in the HashMap.
* If such an element is found, it means there is a pair that sums up to the given sum, so it returns "YES". If no
* such element is found after checking all elements, it returns "NO".
*
* Time Complexity : O(N) // Considering a good hash function without hash collision
* Space Complexity : O(N)
*
* Two-Pointer Approach:
* The array is sorted in ascending order.
* Two pointers, left and right, are initialized to point to the start and end of the array, respectively.
* A loop is used to move the pointers towards each other until they meet. For each position of the pointers, it
* calculates the sum of the elements at left and right.
* If the sum is greater than the given sum, it decrements right to try a smaller sum. If the sum is less than the
* given sum, it increments left to try a larger sum. If the sum is equal to the given sum, it means a pair that sums
* up to the given sum is found, so it returns "YES".
* If no pair is found after the pointers meet, it returns "NO".
*
* Time Complexity : O(N LOG N)
* Space Complexity : O(1)
*/
public class CheckIfAPairExistsWithGivenSum {
public static void main(String[] args) {
int[] arr = {1, 2, 3};
int givenSum = 2;
String b = CheckIfAPairWithGivenSumExistsUsingBruteForce(arr, givenSum);
String b1 = CheckIfAPairWithGivenSumExistsUsingHashMap(arr, givenSum);
String b2 = CheckIfAPairWithGivenSumExistsUsingTwoPointer(arr, givenSum);
System.out.println(b);
System.out.println(b1);
System.out.println(b2);
}
private static String CheckIfAPairWithGivenSumExistsUsingBruteForce(int[] arr, int givenSum) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] == givenSum)
return "YES";
}
}
return "NO";
}
private static String CheckIfAPairWithGivenSumExistsUsingHashMap(int[] arr, int givenSum) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(givenSum - arr[i])) {
return "YES";
}
map.put(arr[i], i);
}
return "NO";
}
private static String CheckIfAPairWithGivenSumExistsUsingTwoPointer(int[] arr, int givenSum) {
Arrays.sort(arr);
int left = 0;
int right = arr.length-1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum > givenSum) {
right--;
}
else if (sum < givenSum) {
left++;
} else {
return "YES";
}
}
return "NO";
}
}
Output : NO
NO
NOProblem: Sort an Array of 0s 1s and 2s using Brute Force
package org.example.Array.Day7;
/**
* The provided Java code is sorting an array of 0s, 1s, and 2s.
* Three counters counter0, counter1, and counter2 are initialized to 0. These counters are used to count the number
* of 0s, 1s, and 2s in the array, respectively.
* A loop is used to iterate over each element in the array. For each element, the corresponding counter is
* incremented.
* After all elements have been counted, another set of loops is used to overwrite the elements in the array. The
* first counter0 elements are set to 0, the next counter1 elements are set to 1, and the remaining counter2 elements
* are set to 2.
* After all elements have been overwritten, the array is sorted.
*
* Time Complexity : O(N)
* Space Complexity : O(1)
*/
public class SortAnArrayOf012sUsingCounter {
public static void main(String[] args) {
int[] arr = {1, 2, 0, 1, 2, 0, 1, 2, 0};
SortAnArrayUsingCounter(arr);
}
private static void SortAnArrayUsingCounter(int[] arr) {
int counter0 = 0;
int counter1 = 0;
int counter2 = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
counter0++;
}
if (arr[i] == 1) {
counter1++;
}
if (arr[i] == 2) {
counter2++;
}
}
for (int i = 0; i < counter0; i++) {
arr[i] = 0;
}
for (int i = 0; i < counter1; i++) {
arr[i + counter0] = 1;
}
for (int i = 0; i < counter2; i++) {
arr[i + counter0 + counter1] = 2;
}
System.out.println(Arrays.toString(arr));
}
}
Output : [0, 0, 0, 1, 1, 1, 2, 2, 2]Problem: Sort an Array of 0s 1s and 2s using Dutch National Flag Algorithm
package org.example.Array.Day7;
/**
* Three pointers low, mid, and high are initialized. low and mid are set to the start of the array, and high is set
* to the end of the array.
* A loop is used to move mid through the array from left to right until it crosses high.
* For each position of mid, the element at mid is checked:
* If the element is 0, it is swapped with the element at low, and then low and mid are incremented.
* If the element is 1, mid is incremented.
* If the element is 2, it is swapped with the element at high, and then high is decremented.
* After all positions of mid have been processed, the array is sorted.
*
* Time Complexity : O(N)
* Space Complexity : O(1)
*/
public class SortAnArrayOf012sUsingDutchNationalFlagAlgo {
public static void main(String[] args) {
int[] arr = {1, 2, 0, 1, 2, 0, 1, 2, 0};
SortAnArrayUsingDutchNationalFlagAlgorithm(arr);
}
private static void SortAnArrayUsingDutchNationalFlagAlgorithm(int[] arr) {
int low = 0;
int mid = 0;
int high = arr.length - 1;
while (mid <= high) {
if (arr[mid] == 0) {
int tmp = arr[low];
arr[low] = arr[mid];
arr[mid] = tmp;
mid++;
low++;
} else if (arr[mid] == 1) {
mid++;
} else {
int tmp = arr[high];
arr[high] = arr[mid];
arr[mid] = tmp;
high--;
}
}
System.out.println(Arrays.toString(arr));
}
}
Output : [0, 0, 0, 1, 1, 1, 2, 2, 2]Problem: Finding an element that occurs more than n/2 times in an array using three different approaches (Brute Force, Hashmap based and Boyer-Moore Voting Algorithm).
package org.example.Array.Day8;
import java.util.HashMap;
import java.util.Map;
/**
* The provided Java code is finding an element that occurs more than n/2 times in an array using three different
* approaches: a brute force approach, a HashMap-based approach, and the Boyer-Moore Voting algorithm. Here are the
* steps for each approach:
* <p>
* Brute Force Approach:
* Two nested loops are used to iterate over the array. The outer loop selects an element, and the inner loop counts
* how many times that element occurs in the array.
* For each element selected by the outer loop, a variable localCount is used to count how many times it occurs in
* the array.
* If localCount is greater than n/2 (where n is the size of the array), the selected element is returned as the
* majority element.
* If no majority element is found after checking all elements, -1 is returned.
*
* Time Complexity : O(N^2)
* Space Complexity : O(1)
*
* HashMap-Based Approach:
* A HashMap is created to count the occurrences of each element in the array.
* A loop is used to iterate over each element in the array. For each element, its count in the HashMap is
* incremented.
* After all elements have been counted, another loop is used to iterate over the entries in the HashMap. If an entry
* with a count greater than n/2 is found, the corresponding element is returned as the majority element.
* If no majority element is found after checking all entries in the HashMap, -1 is returned.
*
* Time Complexity : O(N)
* Space Complexity : O(N)
*
* Boyer-Moore Voting Algorithm:
* Two variables, count and element, are initialized to 0. count is used to keep track of the count of the majority
* candidate, and element is used to store the majority candidate.
* A loop is used to iterate over each element in the array. For each element:
* If count is 0, the current element is set as the majority candidate and count is incremented.
* If the current element is the same as the majority candidate, count is incremented.
* If the current element is different from the majority candidate, count is decremented.
* After all elements have been processed, element holds the majority candidate. However, this does not guarantee
* that element is the majority element, so a second pass over the array is needed to confirm that element occurs
* more than n/2 times.
* In the second pass, a variable newCount is used to count the occurrences of element in the array. If newCount is
* greater than n/2, element is returned as the majority element. Otherwise, -1 is returned.
*
* Time Complexity : O(N)
* Space Complexity : O(1)
*/
public class FindElementOccurMoreThanNBy2 {
public static void main(String[] args) {
int[] arr = {3, 2, 3, 1, 3, 4, 3, 3, 3, 5, 5};
int elementUsingBruteForce = findElementUsingBruteForce(arr);
int elementUsingHashMap = findElementUsingHashMap(arr);
int elementUsingOptimalTechnique = findElementUsingBoyerMooreVotingAlgorithm(arr);
System.out.println(elementUsingBruteForce);
System.out.println(elementUsingHashMap);
System.out.println(elementUsingOptimalTechnique);
}
private static int findElementUsingBoyerMooreVotingAlgorithm(int[] arr) {
int count = 0;
int element = 0;
for (int i = 0; i < arr.length; i++) {
if (count == 0) {
element = arr[i];
count++;
} else if (arr[i] != element) {
count--;
} else {
count++;
}
}
int newCount = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == element) {
newCount++;
}
}
if (newCount > arr.length / 2) {
return element;
}
return element;
}
private static int findElementUsingHashMap(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int value = map.getOrDefault(arr[i], 0);
map.put(arr[i], value + 1);
}
for (Map.Entry<Integer, Integer> it : map.entrySet()) {
if (it.getValue() > arr.length / 2) {
return it.getKey();
}
}
return -1;
}
private static int findElementUsingBruteForce(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int localCount = 0;
for (int j = 0; j < arr.length; j++) {
if (arr[j] == arr[i]) {
localCount++;
}
}
if (localCount > arr.length / 2) {
return arr[i];
}
}
return -1;
}
}
Output : 3
3
3Problem: Finding the maximum sum of a contiguous subarray in an array using different approaches like Brute Force and Kadane’s Algorithm
package org.example.Array.Day8;
/**
* This java code is Finding the maximum sum of a contiguous subarray in an array using two different
* approaches: a brute force approach and the Kadane's algorithm. Here are the steps for each approach: \
* Brute Force Approach:
* Initialize a variable globalSum to 0. This variable is used to store the maximum sum found so far.
* Use two nested loops to generate all possible subarrays of the array.
* For each subarray, calculate the sum of its elements and store it in localSum.
* If localSum is greater than globalSum, update globalSum to localSum.
* Repeat steps 3-4 for all subarrays.
* After all subarrays have been processed, globalSum holds the maximum sum of a contiguous subarray.
*
* Time Complexity : O(N^2)
* Space Complexity : O(1)
*
* Kadane's Algorithm:
* Initialize two variables, sum and maxSum. sum is used to store the current sum of elements, and maxSum is used to
* store the maximum sum found so far.
* Iterate over each element in the array. For each element:
* Add the element to sum.
* Update maxSum to be the maximum of sum and maxSum.
* If sum becomes negative, reset it to 0. This is because a negative sum will not contribute to the maximum sum of a
* future subarray.
* After all elements have been processed, maxSum holds the maximum sum of a contiguous subarray.
* If maxSum is negative (which means all numbers in the array are negative), reset it to 0 because the maximum sum
* of an empty subarray is 0.
* Return maxSum.
*
* Time Complexity : O(N)
* Space Complexity : O(1)
*/
public class MaximumSubArraySumUsingKadaneAlgorithm {
public static void main(String[] args) {
int[] arr = {10, 20, -40, 60, -50, 60};
int maximumSubArraySumUsingBruteForce = findMaximumSubArraySumUsingBruteForce(arr);
long maximumSubArraySumUsingKadaneAlgorithm = findMaximumSubArraySumUsingKadaneAlgorithm(arr);
System.out.println(maximumSubArraySumUsingBruteForce);
System.out.println(maximumSubArraySumUsingKadaneAlgorithm);
}
private static long findMaximumSubArraySumUsingKadaneAlgorithm(int[] arr) {
long sum = 0;
long maxSum = Long.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
sum = sum + arr[i];
maxSum = Math.max(sum, maxSum);
if (sum < 0) {
sum = 0;
}
}
if(maxSum < 0) {
maxSum = 0;
}
return maxSum;
}
private static int findMaximumSubArraySumUsingBruteForce(int[] arr) {
int globalSum = 0;
for (int i = 0; i < arr.length; i++) {
int localSum = 0;
for (int j = i; j < arr.length; j++) {
localSum = localSum + arr[j];
globalSum = Math.max(globalSum, localSum);
}
}
return globalSum;
}
}
Output : 70
70Problem: Finding the maximum sum of a contiguous subarray in an array and returning the subarray itself using Brute Force and Kadane’s Algorithm.
package org.example.Array.Day9;
import java.util.Arrays;
/**
* The provided Java code is finding the maximum sum of a contiguous subarray in an array and returning the subarray
* itself. It uses two different approaches: a brute force approach and the Kadane's algorithm. Here are the steps
* for each approach:
* <p>
* Brute Force Approach:
* Initialize three variables: globalSum to Integer.MIN_VALUE, startIndex to 0, and endIndex to 0. globalSum is used
* to store the maximum sum found so far, and startIndex and endIndex are used to store the start and end indices of
* the subarray with the maximum sum.
* Use two nested loops to generate all possible subarrays of the array. The outer loop selects the start of the
* subarray, and the inner loop selects the end of the subarray.
* For each subarray, calculate the sum of its elements and store it in sum.
* If sum is greater than globalSum, update globalSum to sum and update startIndex and endIndex to the current start
* and end of the subarray.
* After all subarrays have been processed, globalSum holds the maximum sum, and startIndex and endIndex hold the
* start and end indices of the subarray with the maximum sum.
* If globalSum is negative, set startIndex to 1 and endIndex to 0 because the maximum sum of an empty subarray is 0.
* Create a new array newArr and copy the elements from startIndex to endIndex from the original array to newArr.
* Return newArr.
*
* Time Complexity : O(N^2)
* Space Complexity : O(N)
*
* Kadane's Algorithm:
* Initialize four variables: sum to 0, maxSum to Long.MIN_VALUE, startIndex to 0, and endIndex to 0. sum is used to
* store the current sum of elements, maxSum is used to store the maximum sum found so far, and startIndex and
* endIndex are used to store the start and end indices of the subarray with the maximum sum.
* Iterate over each element in the array. For each element:
* Add the element to sum.
* If sum is greater than maxSum, update maxSum to sum and update endIndex to the current index.
* If sum becomes negative, reset sum to 0 and update startIndex to the next index. This is because a negative sum
* will not contribute to the maximum sum of a future subarray.
* After all elements have been processed, maxSum holds the maximum sum, and startIndex and endIndex hold the start
* and end indices of the subarray with the maximum sum.
* If maxSum is negative, set maxSum to 0 because the maximum sum of an empty subarray is 0.
* Create a new array newArr and copy the elements from startIndex to endIndex from the original array to newArr.
* Return newArr.
*
* Time Complexity : O(N)
* Space Complexity : O(N)
*/
public class MaximumSubArraySumPrintArray {
public static void main(String[] args) {
int[] arr = {10, 20, -40, 60, -50, 60};
int[] arr1 = maximumSubarraySumUsingBruteForce(arr);
int[] arr2 = maximumSubarraySumUsingKadaneAlgorithm(arr);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
}
private static int[] maximumSubarraySumUsingKadaneAlgorithm(int[] arr) {
long sum = 0;
long maxSum = Long.MIN_VALUE;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < arr.length; i++) {
sum = sum + arr[i];
if (sum > maxSum) {
maxSum = sum;
endIndex = i;
}
if (sum < 0) {
sum = 0;
startIndex = i + 1;
}
}
if (maxSum < 0) {
maxSum = 0;
}
int[] newArr = new int[endIndex - startIndex + 1];
for (int l = startIndex; l <= endIndex; l++) {
newArr[l - startIndex] = arr[l];
}
return newArr;
}
private static int[] maximumSubarraySumUsingBruteForce(int[] arr) {
int globalSum = Integer.MIN_VALUE;
int startIndex = 0;
int endIndex = 0;
for (int i = 0; i < arr.length; i++) {
int sum = 0;
for (int j = i; j < arr.length; j++) {
sum = sum + arr[j];
if (sum > globalSum) {
globalSum = sum;
startIndex = i;
endIndex = j;
}
}
}
if (globalSum < 0) {
startIndex = 1;
endIndex = 0;
}
int[] newArr = new int[endIndex - startIndex + 1];
for (int l = startIndex; l <= endIndex; l++) {
newArr[l - startIndex] = arr[l];
}
return newArr;
}
}
Output : [60, -50, 60]
[60, -50, 60]Problem: Find maximum profit that can be achieved by buying and selling a stock using Brute-Force and an optimal approach.
package org.example.Array.Day9;
/**
* The provided Java code is finding the maximum profit that can be achieved by buying and selling a stock. It uses
* three different approaches: a brute force approach, a better approach, and an optimal approach. Here are the steps
* for each approach: Brute Force Approach:
* Initialize a variable profit to 0. This variable is used to store the maximum profit found so far.
* Use two nested loops to generate all possible pairs of days. The outer loop represents the day of buying the
* stock, and the inner loop represents the day of selling the stock.
* For each pair of days, calculate the profit (selling price minus buying price) and compare it with profit. If the
* calculated profit is greater than profit, update profit to the calculated profit.
* After all pairs of days have been processed, profit holds the maximum profit that can be achieved.
*
* Time Complexity : O(N^2)
* Space Complexity : O(1)
*
* Better Approach:
* Initialize three variables: buyPrice to Integer.MAX_VALUE, sellPrice to Integer.MIN_VALUE, and profit to 0.
* buyPrice is used to keep track of the minimum price seen so far (which is the best price to buy at), sellPrice is
* used to keep track of the maximum price seen so far after buying a stock (which is the best price to sell at), and
* profit is used to keep track of the maximum profit that can be made.
* Iterate over each price in the array. For each price:
* If the price is less than buyPrice and it's not the last day, update buyPrice to the current price and reset
* sellPrice to Integer.MIN_VALUE. Then, skip to the next iteration.
* If the price is greater than sellPrice, update sellPrice to the current price and update profit to be the maximum
* of the current profit and the difference between sellPrice and buyPrice.
* After all prices have been processed, profit holds the maximum profit that can be made.
*
* Time Complexity : O(N)
* Space Complexity : O(1)
*
* Optimal Approach:
* Initialize two variables: profit to 0 and minimumBuyingPrice to Integer.MAX_VALUE. profit is used to store the
* maximum profit found so far, and minimumBuyingPrice is used to store the minimum price seen so far (which is the
* best price to buy at).
* Iterate over each price in the array. For each price:
* Update minimumBuyingPrice to be the minimum of the current minimumBuyingPrice and the current price.
* Calculate the profit that can be made by selling at the current price (current price minus minimumBuyingPrice),
* and update profit to be the maximum of the current profit and the calculated profit.
* After all prices have been processed, profit holds the maximum profit that can be made.
*
* Time Complexity : O(N)
* Space Complexity : O(1)
*/
public class StockBuyAndSell {
public static void main(String[] args) {
int[] arr = {7, 3, 5, 1, 6, 4};
int profitUsingBruteForce = stockBuyAndSellUsingBruteForce(arr);
int profitUsingBetterApproach = stockBuyAndSellUsingBetterApproach(arr);
int profitUsingOptimalApproach = stockBuyOrSellUsingOptimalApproach(arr);
System.out.println(profitUsingBruteForce);
System.out.println(profitUsingBetterApproach);
System.out.println(profitUsingOptimalApproach);
}
// Sell always happen after buying
private static int stockBuyAndSellUsingBruteForce(int[] arr) {
int profit = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
profit = Math.max(profit, arr[j] - arr[i]);
}
}
return profit;
}
// Sell always happen after buying
private static int stockBuyAndSellUsingBetterApproach(int[] arr) {
int buyPrice = Integer.MAX_VALUE;
int sellPrice = Integer.MIN_VALUE;
int profit = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < buyPrice && i < arr.length - 1) {
buyPrice = arr[i];
sellPrice = Integer.MIN_VALUE; // reset the sell
continue;
}
if (arr[i] > sellPrice) {
sellPrice = arr[i];
profit = Math.max(sellPrice - buyPrice, profit);
}
}
return profit;
}
// Sell always happen after buying
private static int stockBuyOrSellUsingOptimalApproach(int[] arr) {
int profit = 0;
int minimumBuyingPrice = Integer.MAX_VALUE;
for (int sellingDay = 0; sellingDay < arr.length; sellingDay++) {
minimumBuyingPrice = Math.min(minimumBuyingPrice, arr[sellingDay]);
profit = Math.max(profit, arr[sellingDay] - minimumBuyingPrice);
}
return profit;
}
}
Output : 5
5
5For medium level problems part 2, pls see my article
