Scribd
Upload
49 views7 pages

Array Manipulation Techniques in Java

The document contains multiple Java classes that implement various algorithms for array manipulation and analysis. Key functionalities include moving zeros to the end of an array, rotating an array, finding the largest sum contiguous subarray, and checking for duplicates. Each class includes a main method demonstrating the algorithm with sample data.

Uploaded by

22p61a05g7
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
49 views7 pages

Array Manipulation Techniques in Java

The document contains multiple Java classes that implement various algorithms for array manipulation and analysis. Key functionalities include moving zeros to the end of an array, rotating an array, finding the largest sum contiguous subarray, and checking for duplicates. Each class includes a main method demonstrating the algorithm with sample data.

Uploaded by

22p61a05g7
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

3. Move Zeros to the End of the array while maintaining the order of non-zero elements.

public class MoveZeros {


public static void moveZerosToEnd(int[] arr) {
int j = 0;
for (int i = 0; i < [Link]; i++) {
if (arr[i] != 0) {
arr[j++] = arr[i];
}
}
while (j < [Link]) {
arr[j++] = 0;
}
}

public static void main(String[] args) {


int[] arr = {0, 1, 0, 3, 12};
moveZerosToEnd(arr);
[Link]("Array after moving zeros: " + [Link](arr));
}
}

4. Rotate an Array by k Positions to the Right.

public class RotateArray {


public static void rotateArray(int[] arr, int k) {
k = k % [Link];
reverseArray(arr, 0, [Link] - 1);
reverseArray(arr, 0, k - 1);
reverseArray(arr, k, [Link] - 1);
}

private static void reverseArray(int[] arr, int start, int end) {


while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

public static void main(String[] args) {


int[] arr = {1, 2, 3, 4, 5, 6, 7};
int k = 3;
rotateArray(arr, k);
[Link]("Array after rotation: " + [Link](arr));
}
}

5. Find the Largest Sum Contiguous Subarray (Kadane’s Algorithm).

public class KadaneAlgorithm {


public static int maxSubArraySum(int[] arr) {
int maxSum = arr[0], currentSum = arr[0];
for (int i = 1; i < [Link]; i++) {
currentSum = [Link](arr[i], currentSum + arr[i]);
maxSum = [Link](maxSum, currentSum);
}
return maxSum;
}

public static void main(String[] args) {


int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
[Link]("Maximum sum: " + maxSubArraySum(arr));
}
}

14. Find All Pairs in an Array that Sum Up to a Specific Target.

import [Link].*;

public class PairSum {


public static void findPairs(int[] arr, int target) {
Set<Integer> set = new HashSet<>();
for (int num : arr) {
int complement = target - num;
if ([Link](complement)) {
[Link]("Pair: (" + num + ", " + complement + ")");
}
[Link](num);
}
}

public static void main(String[] args) {


int[] arr = {1, 4, 6, 8, 3, 2};
int target = 10;
findPairs(arr, target);
}
}
15. Find the Minimum Product Subarray.

public class MinimumProductSubarray {


public static int minProduct(int[] arr) {
int n = [Link];
int minProd = arr[0], maxProd = arr[0], result = arr[0];

for (int i = 1; i < n; i++) {


if (arr[i] < 0) {
int temp = maxProd;
maxProd = minProd;
minProd = temp;
}

maxProd = [Link](arr[i], maxProd * arr[i]);


minProd = [Link](arr[i], minProd * arr[i]);

result = [Link](result, minProd);


}
return result;
}

public static void main(String[] args) {


int[] arr = {2, 3, -2, 4};
[Link]("Minimum product subarray: " + minProduct(arr));
}
}

16. Find the Minimum Difference Between Any Two Elements in an Array.

import [Link].*;

public class MinimumDifference {


public static int findMinDifference(int[] arr) {
[Link](arr);
int minDiff = Integer.MAX_VALUE;
for (int i = 1; i < [Link]; i++) {
minDiff = [Link](minDiff, arr[i] - arr[i - 1]);
}
return minDiff;
}

public static void main(String[] args) {


int[] arr = {1, 5, 3, 19, 18, 25};
[Link]("Minimum difference: " + findMinDifference(arr));
}
}

20. Find the Subarray with the Maximum Sum (Prefix Sum).

public class MaximumSumSubarray {


public static int maxSubarraySum(int[] arr) {
int maxSum = arr[0], currentSum = arr[0];

for (int i = 1; i < [Link]; i++) {


currentSum = [Link](arr[i], currentSum + arr[i]);
maxSum = [Link](maxSum, currentSum);
}

return maxSum;
}

public static void main(String[] args) {


int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
[Link]("Maximum sum subarray: " + maxSubarraySum(arr));
}
}

24. Find the Sum of the Digits of a Number in an Array.

public class SumOfDigits {


public static int sumOfDigits(int[] arr) {
int sum = 0;
for (int num : arr) {
sum += sumDigits(num);
}
return sum;
}

private static int sumDigits(int num) {


int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}

public static void main(String[] args) {


int[] arr = {123, 456, 789};
[Link]("Sum of digits: " + sumOfDigits(arr));
}
}

25. Reverse an Array In-Place.

public class ReverseArray {


public static void reverse(int[] arr) {
int start = 0, end = [Link] - 1;
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

public static void main(String[] args) {


int[] arr = {1, 2, 3, 4, 5};
reverse(arr);
[Link]("Reversed array: " + [Link](arr));
}
}

26. Check if an Array is Palindrome.

public class PalindromeArray {


public static boolean isPalindrome(int[] arr) {
int start = 0, end = [Link] - 1;
while (start < end) {
if (arr[start] != arr[end]) {
return false;
}
start++;
end--;
}
return true;
}

public static void main(String[] args) {


int[] arr = {1, 2, 3, 2, 1};
[Link]("Is palindrome: " + isPalindrome(arr));
}
}

27. Check if an Array is Sorted.

public class SortedArray {


public static boolean isSorted(int[] arr) {
for (int i = 1; i < [Link]; i++) {
if (arr[i - 1] > arr[i]) {
return false;
}
}
return true;
}

public static void main(String[] args) {


int[] arr = {1, 2, 3, 4, 5};
[Link]("Is array sorted? " + isSorted(arr));
}
}

29. Find the Pair with the Smallest Difference in an Array.

import [Link].*;

public class SmallestDifferencePair {


public static int[] findSmallestPair(int[] arr) {
[Link](arr);
int minDiff = Integer.MAX_VALUE;
int[] pair = new int[2];

for (int i = 1; i < [Link]; i++) {


int diff = arr[i] - arr[i - 1];
if (diff < minDiff) {
minDiff = diff;
pair[0] = arr[i - 1];
pair[1] = arr[i];
}
}

return pair;
}

public static void main(String[] args) {


int[] arr = {1, 5, 9, 13, 17};
[Link]("Pair with smallest difference: " +
[Link](findSmallestPair(arr)));
}
}

31. Check if an Array Contains Duplicate Elements.


import [Link].*;

public class ContainsDuplicate {


public static boolean containsDuplicate(int[] arr) {
Set<Integer> set = new HashSet<>();
for (int num : arr) {
if ([Link](num)) {
return true;
}
[Link](num);
}
return false;
}

public static void main(String[] args) {


int[] arr = {1, 2, 3, 4, 2};
[Link]("Contains duplicate: " + containsDuplicate(arr));
}
}

Common questions

Powered by AI

The logic involves using a hash set to track elements that have already been encountered. As the array is iterated over, each element is checked against the hash set. If the element is already present, it indicates a duplicate and returns true; if not, the element is added to the set. This method ensures efficient duplicate detection by leveraging the constant time lookups provided by hash sets .

To find the minimum product subarray, the method employs two variables, minProd and maxProd, which track the minimum and maximum product ending at the current position, respectively. It also considers the role of negative numbers by swapping maxProd and minProd when a negative number is encountered because a negative number can turn a small minimum product into a large one, and vice-versa. This approach effectively navigates the sign change caused by multiplication with negative numbers, ensuring that both potential maxima and minima are considered at each step .

Sorting the array arranges the elements in increasing order, allowing the smallest difference to occur between consecutive elements. This ordered sequence enables efficient checking of differences between successive elements, and thus, easily finding the minimum difference among all possible pairs .

The sum of digits is calculated by iterating over each number in the array, breaking it down into individual digits, and adding these digits together. This involves repeatedly obtaining the last digit using modulo 10 and then removing it from the number using integer division by 10, until all digits are summed .

To determine if an array is sorted, the technique iterates through the array and checks if each element at position i-1 is less than or equal to the element at position i. If all such comparisons hold true through the array, it is sorted, else it is not .

Reversing the entire array initially in k-position rotation switches the order of all elements, setting up the array such that subsequent partial reversals correctly position elements in their final rotated order. This initial reversal is a critical transformation step that aligns the elements to be moved in their new order, thus simplifying the overall rotation process .

Kadane's Algorithm calculates the largest sum contiguous subarray by iterating through the array and maintaining two variables, maxSum and currentSum. It updates currentSum by taking the maximum of arr[i] alone or adding arr[i] to the currentSum, and updates maxSum with the greater value between maxSum and currentSum at each step. This ensures that the algorithm efficiently checks all possible subarray sums in a linear scan .

The strategy uses a hash set to store the complements of array elements with respect to the target. As each element is processed, the hash set checks if its complement (target minus the current element's value) already exists in the set. This allows for constant time lookup operations to find pairs efficiently, significantly reducing the overall computational complexity .

The approach to rotate an array by k positions to the right involves three reverse operations. First, reverse the entire array. Then, reverse the first k elements, followed by reversing the remaining elements from k to the end of the array. This sequence effectively shifts the array elements to the right by k positions, as reversing subarrays changes their order respective to the rotation requirement .

The method maintains the order of non-zero elements by using a write index, j, which only increments when a non-zero element is encountered. Each non-zero element is moved to the position indicated by j, which preserves the sequence in which non-zero elements appear originally. Any remaining positions in the array are filled with zeros once all non-zero elements have been repositioned .

You might also like