Solving the Square of a Rotated Array Problem

In this blog post, we delve into the “Square of a Rotated Array” problem from LeetCode, providing a comprehensive solution using Java. Learn how to efficiently square each element of a rotated sorted array and return the result in sorted order. We explore the two-pointer technique to achieve an optimal solution with clear and concise Java code.

Introduction

In this blog post, we will explore a solution to the “Square of a Rotated Array” problem from LeetCode using Java. This problem involves taking a rotated sorted array of integers, squaring each element, and then returning a new array that contains these squared values in sorted order

Problem Statement

Given a rotated sorted array nums, return an array of the squares of each number sorted in non-decreasing order.

Approach

To solve this problem, we can use a two-pointer approach. We will maintain two pointers, one starting from the beginning and the other from the end of the array. We will compare the absolute values of the elements at these pointers, square the larger value, and insert it into the result array from the end to the beginning. This ensures that the largest squared values are placed at the end, thus maintaining the sorted order.

Steps to Solve the Problem

1. Initialize two pointers, left and right, at the beginning and end of the array, respectively.
2. Create a result array of the same length as the input array.
3. Iterate through the input array in reverse order.
4. Compare the absolute values of the elements at the left and right pointers.
5. Square the larger value and insert it into the result array.
6. Move the pointer corresponding to the larger value inward.
7. Return the result array.

Java Implementation

import java.util.Arrays;

public class SquareOfRotatedArray {
public static int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] result = new int[n];
int left = 0;
int right = n – 1;
int index = n – 1;

    while (left <= right) {
        int leftSquare = nums[left] * nums[left];
        int rightSquare = nums[right] * nums[right];

        if (leftSquare > rightSquare) {
            result[index] = leftSquare;
            left++;
        } else {
            result[index] = rightSquare;
            right--;
        }
        index--;
    }

    return result;
}

public static void main(String[] args) {
    int[] nums = {-4, -1, 0, 3, 10};
    int[] squaredSortedArray = sortedSquares(nums);
    System.out.println("Input array: " + Arrays.toString(nums));
    System.out.println("Squared and sorted array: " + Arrays.toString(squaredSortedArray));
}

}

Explanation

• Initialization: We initialize two pointers, left at the start and right at the end of the array. We also create a result array to store the squared values in sorted order.
• Iteration: We iterate from the end of the result array towards the beginning.
• Comparison: We compare the squares of the elements at the left and right pointers.
• Insertion: We insert the larger squared value into the current position in the result array and move the corresponding pointer inward.
• Output: Finally, we return the result array containing the squared values in non-decreasing order.

Conclusion

This approach efficiently solves the “Square of a Rotated Array” problem using a two-pointer technique, ensuring that the time complexity is O(n), where n is the length of the input array. This method avoids the need for additional sorting, making it both time and space efficient.

By following this approach, you can easily handle arrays with negative, zero, and positive values, ensuring that the squared results are always sorted in non-decreasing order.

Read More…

Backracking | Data Structures & Algorithms Tutorials – https://kamleshsingad.com/backracking-data-structures-algorithms-tutorials/

What is Dynamic Programming? Working, Algorithms, and Examples – https://kamleshsingad.com/what-is-dynamic-programming-working-algorithms-and-examples/

Greedy Algorithm – https://kamleshsingad.com/greedy-algorithm/