1610. Maximum Number of Visible Points - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an integer array nums sorted in non-decreasing order. Your task is to return an array of the squares of each number, also sorted in non-decreasing order.

Key Points:

The array can include negative numbers.
Squaring negative numbers will produce positive values, which may disrupt the original order.
The challenge is to efficiently generate the sorted squared values without simply squaring and then re-sorting.

Constraints:

The length of nums is at least 1.
nums is sorted in non-decreasing order.
The array can contain negative numbers, zero, and positive numbers.

Example 1:

Input: nums = [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]
Explanation:
Squaring the elements gives [16, 1, 0, 9, 100]. After sorting these values in non-decreasing order, we get [0, 1, 9, 16, 100].

Example 2:

Input: nums = [-7, -3, 2, 3, 11]
Output: [4, 9, 9, 49, 121]
Explanation:
Squaring the elements gives [49, 9, 4, 9, 121]. Sorting these yields [4, 9, 9, 49, 121].

Example 3:

Input: nums = [1, 2, 3, 4, 5]
Output: [1, 4, 9, 16, 25]
Explanation:
Since all numbers are positive, their squares are already in non-decreasing order after squaring.

Hints

Hint 1: Although the original array is sorted, once you square the elements, the relative order may change. Consider how the largest absolute values (which might be negative) will produce the largest squares.
Hint 2: Use a two-pointer approach. One pointer at the beginning and one at the end of the array will allow you to compare the absolute values. Place the square of the larger absolute value at the end of your result array and move the corresponding pointer inward.

Approaches

Approach 1: Brute Force

Idea:
- Square every element in the array.
- Sort the resulting array.
How It Works:
1. Traverse the array, computing the square of each element.
2. Use a sorting algorithm (or built-in sort) to sort the squared values.
Complexity:
- Time Complexity: O(n log n) due to the sorting step.
- Space Complexity: O(n) for the result array.
Drawback:
- While simple, this approach is not optimal for large arrays.

Approach 2: Two-Pointer Technique (Optimal Approach)

Idea:
- Use two pointers, one at the beginning (left) and one at the end (right) of the array.
- The largest square comes from the number with the larger absolute value.
- Fill the result array from the end to the beginning by comparing the absolute values at the two pointers.
How It Works:
1. Initialize left at the start and right at the end of the array.
2. Create a result array of the same length.
3. Compare abs(nums[left]) and abs(nums[right]). The larger absolute value, when squared, will be placed at the current end of the result array.
4. Move the corresponding pointer inward.
5. Repeat until left exceeds right.
Complexity:
- Time Complexity: O(n) since we only traverse the array once.
- Space Complexity: O(n) for the output array.
Benefit:
- This approach avoids the extra sorting step and is optimal for the problem.

Python Code

Python3

. . . .

Java Code

Below is the Java implementation using the two-pointer approach.

Java

. . . .

Complexity Analysis

Time Complexity:
- Brute Force: O(n log n) because of the sorting step.
- Two-Pointer Technique: O(n) since it makes a single pass through the array.
Space Complexity:
- Both approaches require O(n) additional space for the result array.
- The two-pointer method does not use extra space beyond the output.

Step-by-Step Walkthrough & Visual Example

Consider the input nums = [-4, -1, 0, 3, 10]:

Initialization:
- left = 0 (points to -4)
- right = 4 (points to 10)
- result = [0, 0, 0, 0, 0]
- position = 4 (start filling from the end)
First Iteration:
- Compare: abs(-4) = 4 vs. abs(10) = 10
- Square larger absolute value (10): $(10^2 = 100)$
- Place 100 at result[4], then decrement right to 3 and position to 3.
- Result now: [0, 0, 0, 0, 100]
Second Iteration:
- Compare: abs(-4) = 4 vs. abs(3) = 3
- Square larger absolute value (-4): $((-4)^2 = 16)$
- Place 16 at result[3], then increment left to 1 and decrement position to 2.
- Result now: [0, 0, 0, 16, 100]
Third Iteration:
- Compare: abs(-1) = 1 vs. abs(3) = 3
- Square larger absolute value (3): $(3^2 = 9)$
- Place 9 at result[2], then decrement right to 2 and position to 1.
- Result now: [0, 0, 9, 16, 100]
Fourth Iteration:
- Now left = 1 (points to -1) and right = 2 (points to 0)
- Compare: abs(-1) = 1 vs. abs(0) = 0
- Square larger absolute value (-1): $((-1)^2 = 1)$
- Place 1 at result[1], then increment left to 2 and decrement position to 0.
- Result now: [0, 1, 9, 16, 100]
Final Iteration:
- With left = right = 2 (pointing to 0)
- Square: $(0^2 = 0)$
- Place 0 at result[0], then update pointers.
- Final result: [0, 1, 9, 16, 100]

Common Mistakes, Edge Cases & Alternative Variations

Common Mistakes:

Sorting after Squaring:
A straightforward approach might square each element and then sort the array. While correct, it is less efficient than the two-pointer method.
Incorrect Pointer Movement:
Failing to properly update the left/right pointers based on the comparison of absolute values can lead to an incorrect result.
Overlooking Negative Numbers:
Not handling negative values correctly may cause the algorithm to miss larger squares generated from negatives.

Edge Cases:

Empty Array:
Although the constraints guarantee at least one element, it is good practice to handle or document what happens when the array is empty.
All Positive or All Negative:
When the array is all positive, the two-pointer approach works similarly to a single pass. When all negative, the largest (in absolute) is at the beginning.
Single Element:
The result is simply the square of that element.

Alternative Variations:

In-Place Squaring (if allowed):
Modifying the input array in place if extra space is restricted.
Merging Two Sorted Arrays:
Conceptually similar when merging two sorted halves—one for negative squares (reversed) and one for non-negative squares.

Two Sum II - Input Array Is Sorted:
Uses the two-pointer technique to find a pair of numbers that add up to a target.
Merge Sorted Array:
Merging two sorted arrays into one sorted array.
Sorted Merge of Two Arrays:
Similar in concept, often appearing in interview scenarios.
Find the K-th Largest Element in a Sorted Matrix:
Involves similar strategies of comparing elements from different ends.