Day 6 of 100 Days of DSA Challenge: Arrays - Problems

Today's challenges involved advanced array manipulations, focusing on optimizing space and time complexity. Here’s an overview of the problems and their solutions.

1. Rotate an Array by k Steps to the Right (O(n) Time, No Extra Space)

Rotate the array elements to the right by k positions using an efficient algorithm

without additional memory.

import java.util.Scanner;

public class RotateArray {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of elements in array: ");
        int length = sc.nextInt();
        int[] arr = new int[length];
        System.out.print("Enter the value of k: ");
        int k = sc.nextInt();

        System.out.println("Enter the elements of the array: ");
        for(int i=0; i<length; i++){
            if(i<=k)
                arr[i+k] = sc.nextInt();
            else
                arr[i-k-1] = sc.nextInt();
        }

        System.out.println("Array after rotation: ");
        for (int i = 0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }
}

2. Find the Missing Number in an Array of Size n-1 (O(n) Time)

Identify the missing number in an array containing n−1 distinct integers from the

range 1 to n, leveraging mathematical properties or XOR.

import java.util.Scanner;

public class MissingNumber {
    public static int findMissingNumber(int[] arr, int n) {
        int totalSum = n * (n + 1) / 2; 
        int arraySum = 0;
        for (int num : arr) {
            arraySum += num;
        }
        return totalSum - arraySum;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the value of n: ");
        int n = sc.nextInt();
        int[] arr = new int[n-1];
        System.out.println("Enter elements of the arry: ");
        for(int i=0; i<n-1; i++)
            arr[i] = sc.nextInt();

        System.out.println("Missing Number: " + findMissingNumber(arr, n));
    }
}

3. Rearrange Array Alternately (Largest, Smallest, Second Largest, etc.) in O(n) Time

Rearrange an array in a zig-zag pattern without using additional space, maintaining O(n)O(n) complexity.

import java.util.Scanner;

public class MaximumSubArraySum {
    public static int maxSubArraySum(int[] arr) {
        int maxSoFar = arr[0];
        int currentMax = arr[0];

        for (int i = 1; i < arr.length; i++) {
            currentMax = Math.max(arr[i], currentMax + arr[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }

        return maxSoFar;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of elements: ");
        int n = sc.nextInt();
        int[] arr = new int[n];
        System.out.println("Enter elements of the arry: ");
        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();

        System.out.println("Maximum Subarray Sum: " + maxSubArraySum(arr));
    }
}

4. Contiguous Subarray with Maximum Sum in O(n) Time

Use Kadane’s Algorithm to determine the subarray with the maximum sum in linear time.

5. Count Frequency of Each Element in O(n) Time Without Extra Space

Count the occurrences of each element in the array efficiently by temporarily modifying the array.

import java.util.Scanner;

public class FrequencyCounter {
    public static void countFrequencies(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            arr[i]--;
        }

        for (int i = 0; i < n; i++) {
            arr[arr[i] % n] += n;
        }

        System.out.println("Frequencies:");
        for (int i = 0; i < n; i++) {
            System.out.println((i + 1) + " -> " + arr[i] / n);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of elements: ");
        int n = sc.nextInt();
        int[] arr = new int[n];
        System.out.println("Enter elements of the arry: ");
        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();
        countFrequencies(arr);
    }
}

Reflection

Day 6 presented a mix of algorithmic challenges that tested my understanding of array manipulation and optimization techniques. I found the tasks involving in-place rearrangement and counting frequencies particularly rewarding as they push for creativity in working within constraints.

Excited for what Day 7 brings! 🚀