Chapter 2 : Mastering Arrays: A Key to Cracking FAANG DSA Interviews

Welcome to Chapter 2 of our DSA in Java journey! Today, we'll delve into arrays, one of the fundamental building blocks of programming and a crucial concept for FAANG interview success.

2.1: What are Arrays?

An array is a data structure used in programming to store a fixed-size sequence of elements of the same type. Each element in an array is identified by its index (or position) within the array, starting from 0.

2.2: Why are Arrays Important for FAANG Preparation?

Arrays are versatile and efficient for manipulating large sets of data. Understanding how to declare, initialize, access, and modify elements in arrays is vital for various programming tasks. Many FAANG interview questions involve manipulating data using arrays, making it a key concept to master.

2.3: Let's Explore Arrays in Action:

1. Declaring and Initializing an Array:

    int[] numbers = new int[5]; // Declares an array of integers with size 5
    String[] names = {"Alice", "Bob", "Charlie"}; // Directly initializes an array of strings
   

2. Accessing and Modifying Elements:

    numbers[0] = 10; // Assigns the value 10 to the element at index 0 (first box) System.out.println(names[1]); // Prints the element at index 1 (second box)2.4:Key Array Problems for Interviews
   

2.4:Key Array Problems for Interviews

To solidify your understanding of arrays, let’s discuss some essential array-based problems commonly asked in FAANG interviews.

2.4.1:roblem 1: Best Time to Buy and Sell Stock. (Difficult-Level:Medium)

Problem Summary: Given an array prices where prices[i] represent the stock price on day i, the goal is to find the maximum profit you can achieve by choosing a day to buy and a later day to sell. You cannot sell before buying.

Example:

Input: prices = {7, 1, 5, 3, 6, 4} 
Output: 5 // Buy at 1 and sell at 6

Approach:

1. Track the Minimum Buy Price:

   • Initialize buyPrice with a very high value (Integer.MAX_VALUE).

   • As you iterate over prices, update buyPrice to the lowest price encountered so far. This keeps track of the cheapest price to buy.

2. Calculate the Profit at Each Step:

   • For each day's price, calculate the profit by subtracting the buyPrice (lowest price so far) from the current day’s price (prices[i]).

   • If this calculated profit is greater than the current maxProfit, update maxProfit to this new value.

3. Greedy Choice:

   • This algorithm updates buyPrice only when a lower price is found and updates maxProfit only when a higher profit is possible.

Java Code Implementation:

public class SellAndBuy {
public static int stocks(int[] prices) {
        int buyPrice = Integer.MAX_VALUE; // Minimum price to buy
        int maxProfit = 0; // Maximum profit so far

        for (int i = 0; i < prices.length; i++) {
            // Update buyPrice to the lowest price seen so far
            if (prices[i] < buyPrice) {
                buyPrice = prices[i];
            } else {
                // Calculate profit if selling at the current price
                int profit = prices[i] - buyPrice;
                maxProfit = Math.max(maxProfit, profit);
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(stocks(prices)); // Expected output: 5
    }
}

Output : 5

Complexity Analysis:

• Time Complexity: O(n), as it makes a single pass through the array.

• Space Complexity: O(1), requiring only a few tracking variables.

---

2.4.2:Problem 2 : Trapping Rain Water problem. (Difficult-Level:Hard)

Problem Summary:

Given an array height[], where each element represents the elevation at that index, calculate the total water trapped after it rains.

Approach:

This solution uses the left and right maximum boundary approach, which allows us to efficiently calculate the trapped water at each index. The idea is to determine the maximum height to the left and right of each element and use this information to compute the trapped water at that position.

1. Compute Left Maximums:

   • LeftMax[i] holds the maximum height to the left of or at index i.

   • Traverse the array from left to right, filling LeftMax by taking the maximum of the current height and the previous maximum.

2. Compute Right Maximums:

   • RightMax[i] holds the maximum height to the right of or at index i.

   • Traverse the array from right to left, filling RightMax by taking the maximum of the current height and the next maximum.

3. Calculate Trapped Water:

   • For each index i, the trapped water is determined by the minimum of LeftMax[i] and RightMax[i] minus the height at i.

   • Sum up the trapped water for each index to get the total amount.

Java Code Implementation:

package Array; 
public class trapwater {
public static int trappedRainWater(int height[]) {
        int LeftMax[] = new int[height.length];
        LeftMax[0] = height[0];
        for(int i = 1; i < height.length; i++) {
            LeftMax[i] = Math.max(height[i], LeftMax[i - 1]);
        }

        int RightMax[] = new int[height.length];
        RightMax[height.length - 1] = height[height.length - 1];
        for(int i = height.length - 2; i >= 0; i--) {
            RightMax[i] = Math.max(height[i], RightMax[i + 1]);
        }

        int trappedWater = 0;
        for(int i = 0; i < height.length; i++) {
            int waterLevel = Math.min(LeftMax[i], RightMax[i]);
            trappedWater += waterLevel - height[i];
        }
        return trappedWater;
    }

    public static void main(String[] args) {
        int height[] = {4, 2, 0, 6, 3, 2, 5};
        System.out.println(trappedRainWater(height));
    }
}

Output : 11

Example Walkthrough:

For height = {4, 2, 0, 6, 3, 2, 5}, the output is 11 ,as calculated by summing up the trapped water at each index.

Total trapped water =0+ 2+4+0+2+3=11

Complexity Analysis

• Time Complexity: O(n), as we traverse the array three times (to fill LeftMax, RightMax, and calculate trapped water).

• Space Complexity: O(n), for the LeftMax and RightMax arrays.

---

2.4.3:Problem 3 : Maximum Subarray (Kadane's Algorithm). (Difficult-Level:Hard)

Problem Summary: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Approach: Kadane’s Algorithm

Kadane’s Algorithm uses a dynamic programming approach to keep track of the maximum sum ending at each position. Here's the breakdown of the approach:

1. Initialize Variables:

   • maxSum to store the maximum sum found so far, initialized to the first element of the array.

   • currentSum to store the current subarray sum, also initialized to the first element.

2. Iterate Over the Array:

   • For each element nums[i], update currentSum as the maximum of nums[i] alone (starting a new subarray) or currentSum + nums[i] (extending the existing subarray).

   • Update maxSum to be the maximum of currentSum and maxSum.

3. Result:

   • After iterating through the array, maxSum will contain the largest sum of any contiguous subarray.

Java Code Implementation:

public class MaxSubArray {
public static int maxSubArray(int[] nums) {
        int maxSum = nums[0]; // Initialize max sum to the first element
        int currentSum = nums[0]; // Initialize current sum to the first element

        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]); // Extend or start new subarray
            maxSum = Math.max(maxSum, currentSum); // Update maxSum if currentSum is larger
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum Subarray Sum: " + maxSubArray(nums)); // Output: 6
    }
}

Output:6 (The subarray [4, -1, 2, 1] has the largest sum = 6)

Example Walkthrough

Let’s go through nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] step-by-step:

Final maxSum = 6, which is the maximum sum of the subarray [4, -1, 2, 1].

Complexity Analysis

• Time Complexity: O(n)O(n)O(n), as we iterate through the array once.

• Space Complexity: O(1)O(1)O(1), since we only use a few extra variables (maxSum and currentSum).

---

2.4.4:Problem 4:Revers a given array. (Difficult-Level: Easy)

Problem Summary:

To reverse an array, we need to swap elements from the beginning and end of the array until we reach the middle. This can be done efficiently using a two-pointer approach, which gives us an O(n)O(n)O(n) time complexity, where nnn is the length of the array.

Approach

1. Initialize Two Pointers:

   • Start one pointer at the beginning of the array (left = 0).

   • Start the other pointer at the end of the array (right = array.length - 1).

2. Swap Elements:

   • Swap the elements at the left and right pointers.

   • Move the left pointer one step to the right (left++).

   • Move the right pointer one step to the left (right--).

3. Continue Until the Pointers Meet:

   • Repeat the swapping until left is no longer less than right. At this point, the array is reversed.

Java Code Implementation:package Array;

package Array;
// REVERSE AN ARRAY
public class ReversAraay {
    public static void revers(int number[]){
        int first=0;// Start pointer at the beginning
        int last = number.length-1;// End pointer at the end

        while (first < last) {
            //Swap elements at left and right
            int temp = number[last];
            number[last]=number[first];
            number[first]=temp;

            first++;
            last--;
        }
    }
    public static void main(String[] args) {
        int number[]={25,20,15,10,5};

        revers(number);// Call to reverse the array
        for(int i=0;i<number.length;i++){
            System.out.print(number[i]+" ");
        }
        System.out.println();
    }
}

Output:5 10 15 20 25

Explanation of the Code

1. reverse(int[] array): This function reverses the array in place by swapping elements from the two ends.

2. main Method: Initializes the array, displays the original, reverses it using reverse(), and then prints the reversed array.

Example

For the input array {25,20,15,10,5}, the output would be:

 Original Array: 25,20,15,10,5
 Reversed Array: 5,10,15,20,25

Complexity Analysis

• Time Complexity: O(n)O(n)O(n), where nnn is the length of the array, since we traverse half the array to complete the reversal.

• Space Complexity: O(1)O(1)O(1), as the reversal is done in place without needing extra space.

---

**2.4.5:Problem 5:**Remove duplicates from a sorted array.(Difficult-level:Easy)

Problem Summary:

To remove duplicates from a sorted array in Java, you can use a two-pointer technique to efficiently solve the problem in O(n) time. Here's a step-by-step explanation followed by the code:

Approach:

1. Use two pointers:

   • i to track the index of the last unique element in the array.

   • j to iterate through the array.

2. Compare the current element (arr[j]) with the last unique element (arr[i]).

3. If they are different, increment i and update arr[i] to arr[j].

4. At the end, the first i + 1 elements of the array will contain the unique elements.

Java Code Implementation:

public class RemoveDuplicates {

    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0; // If array is empty, return 0
        }

        int i = 0; // Pointer for unique elements
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++; // Move the unique pointer
                nums[i] = nums[j]; // Update the unique element
            }
        }
        return i + 1; // Length of the array with unique elements
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 3, 3, 4, 5, 5, 6};
        int length = removeDuplicates(nums);

        System.out.println("Array after removing duplicates:");
        for (int k = 0; k < length; k++) {
            System.out.print(nums[k] + " ");
        }
    }
}

Output:

For the input array {1, 1, 2, 3, 3, 4, 5, 5, 6}, the output will be:

javascriptCopy codeArray after removing duplicates:
1 2 3 4 5 6

Explanation:

• The input array is modified in-place to contain only the unique elements at the beginning.

• The function returns the count of unique elements, which helps to identify the valid part of the modified array.

---