FastPrepK Smallest Squares from a Sorted Array
Problems/K Smallest Squares from a Sorted Array

K Smallest Squares from a Sorted Array

Uber logoUber● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The interview report asks for squared values and then the smallest k squares from a sorted array using binary-search reasoning. The ordered 64-bit result makes the optimization directly executable.

Given an integer array sorted in nondecreasing order, return the k smallest squared values in nondecreasing order.

Use 64-bit arithmetic for every square. The intended solution locates the split between negative and nonnegative values with binary search and merges outward from that split without materializing and sorting all squared values.

Function

kSmallestSquares(nums: int[], k: int) → long[]

Examples

Example 1

nums = [-7,-3,-1,4,8]k = 3return = [1,9,16]

The three smallest squares come from -1, -3, and 4.

Example 2

nums = [-2,-2,0,3]k = 4return = [0,4,4,9]

Duplicate input magnitudes produce duplicate squares.

Example 3

nums = [-1000000000,2]k = 1return = [4]

The square of 2 is smaller; 64-bit arithmetic is required for the other value.

Constraints

  • 0 <= nums.length <= 200000.
  • 0 <= k <= nums.length.
  • -10^9 <= nums[i] <= 10^9.
  • nums is sorted in nondecreasing order.

More Uber problems

  • Worst-Performing Ads by CTR in a Campaign TreePHONE SCREEN · Seen Nov 2026
  • Earliest Time All Users Are ConnectedPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Max Points on a LinePHONE SCREEN · Seen Oct 2026
All Uber interview questionsSee Uber hiring insights
Saved
class Solution {
    public long[] kSmallestSquares(int[] nums, int k) {
        // Write your solution here.
    }
}
Checking account…