On Day 3 of my 100 Days of DSA challenge, I delved into advanced array problems. These problems required a deeper understanding of algorithms and efficient data manipulation techniques. Below are the problems and their Java solutions.
1. Merge Two Sorted Arrays
The goal is to merge two sorted arrays into one sorted array efficiently.
import java.util.Scanner;
public class MergeSortedArrays {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter number of elements in arr1: ");
int count1 = sc.nextInt();
System.out.print("Enter number of elements in arr2: ");
int count2 = sc.nextInt();
int[] arr1 = new int[count1];
int[] arr2 = new int[count2];
System.out.println("Enter elements of arr1: ");
for(int i=0; i<count1; i++)
arr1[i] = sc.nextInt();
System.out.println("Enter elements of arr2: ");
for(int i=0; i<count2; i++)
arr2[i] = sc.nextInt();
int[] ans = new int[count1+count2];
int len=0;
int i=0, j=0;
while(i<count1 || j<count2){
if(i==count1){
ans[len] = arr2[j];
j++;
len++;
}else if(j==count2){
ans[len] = arr1[i];
i++;
len++;
}else if(arr1[i]<arr2[j]){
ans[len] = arr1[i];
i++;
len++;
}else{
ans[len] = arr2[j];
j++;
len++;
}
}
for(i=0; i<count1+count2; i++)
System.out.print(ans[i]+" ");
}
}
2. Find the Union and Intersection of Two Arrays
The union contains all unique elements from both arrays, and the intersection contains elements common to both arrays.
import java.util.Arrays;
import java.util.Scanner;
public class UnionIntersection {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter number of elements in arr1: ");
int count1 = sc.nextInt();
System.out.print("Enter number of elements in arr2: ");
int count2 = sc.nextInt();
int[] arr1 = new int[count1];
int[] arr2 = new int[count2];
System.out.println("Enter the elements of arr1: ");
for(int i=0; i<count1; i++)
arr1[i] = sc.nextInt();
System.out.println("Enter the elements of arr2: ");
for(int i=0; i<count2; i++)
arr2[i] = sc.nextInt();
System.out.println("Union: " + Arrays.toString(findUnion(arr1, arr2)));
System.out.println("Intersection: " + Arrays.toString(findIntersection(arr1, arr2)));
}
public static int[] findUnion(int[] arr1, int[] arr2) {
int[] temp = new int[arr1.length + arr2.length];
int index = 0;
for (int num : arr1) {
temp[index++] = num;
}
for (int num : arr2) {
temp[index++] = num;
}
Arrays.sort(temp);
int[] result = new int[temp.length];
int resIndex = 0;
for (int i = 0; i < temp.length; i++) {
if (i == 0 || temp[i] != temp[i - 1]) {
result[resIndex++] = temp[i];
}
}
return Arrays.copyOf(result, resIndex);
}
public static int[] findIntersection(int[] arr1, int[] arr2) {
Arrays.sort(arr1);
Arrays.sort(arr2);
int i = 0, j = 0;
int[] temp = new int[Math.min(arr1.length, arr2.length)];
int index = 0;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
i++;
} else if (arr1[i] > arr2[j]) {
j++;
} else {
if (index == 0 || temp[index - 1] != arr1[i]) {
temp[index++] = arr1[i];
}
i++;
j++;
}
}
return Arrays.copyOf(temp, index);
}
}
3. Find a Subarray with a Given Sum (Positive Numbers)
The task is to find a contiguous subarray that sums up to a given target value.
import java.util.Scanner;
public class SubarrayWithSum {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter number of elements in the array: ");
int count = sc.nextInt();
System.out.println("Enter elements of the array: ");
int[] arr = new int[count];
for(int i=0; i<count; i++)
arr[i] = sc.nextInt();
System.out.print("Enter the target: ");
int target = sc.nextInt();
int start = 0, sum = 0;
for (int end = 0; end < arr.length; end++) {
sum += arr[end];
while (sum > target) sum -= arr[start++];
if (sum == target) {
System.out.println("Subarray found from index " + start + " to " + end);
return;
}
}
System.out.println("No subarray with the given sum found.");
}
}
4. Kadane’s Algorithm for Maximum Sum Subarray
Kadane's algorithm efficiently finds the maximum sum of a contiguous subarray in O(n) time.
public class KadanesAlgorithm {
public static void main(String[] args) {
int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSum = arr[0], currentSum = arr[0];
for (int i = 1; i < arr.length; i++) {
currentSum = Math.max(arr[i], currentSum + arr[i]);
maxSum = Math.max(maxSum, currentSum);
}
System.out.println("Maximum Sum Subarray: " + maxSum);
}
}
5. Rearrange an Array with Alternate Positive and Negative Numbers
The task is to rearrange the array so that positive and negative numbers alternate, maintaining relative order.
import java.util.Scanner;
public class AlternatePositiveNegative {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter number of elements in the array: ");
int count = sc.nextInt();
System.out.println("Enter elements of the array: ");
int[] arr = new int[count];
for(int i=0; i<count; i++)
arr[i] = sc.nextInt();
rearrangeAlternate(arr);
System.out.print("Rearranged Array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void rearrangeAlternate(int[] arr) {
int n = arr.length;
int[] positives = new int[n];
int[] negatives = new int[n];
int posIndex = 0, negIndex = 0;
for (int num : arr) {
if (num >= 0) {
positives[posIndex++] = num;
} else {
negatives[negIndex++] = num;
}
}
int i = 0, p = 0, q = 0;
while (p < posIndex && q < negIndex) {
arr[i++] = positives[p++];
arr[i++] = negatives[q++];
}
while (p < posIndex) {
arr[i++] = positives[p++];
}
while (q < negIndex) {
arr[i++] = negatives[q++];
}
}
}
Reflection
Today’s problems were both challenging and enlightening. The concepts of merging, efficient searching, and array rearrangement are essential for solving real-world problems and acing coding interviews. I particularly enjoyed implementing Kadane’s Algorithm for its elegance and efficiency.
Looking forward to exploring more challenges on Day 4! 🚀