FastPrepMerge Sorted Squares of Two Arrays

Merge Sorted Squares of Two Arrays

WhatNot logoWhatNot● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Given two integer arrays a and b, each sorted in nondecreasing order, return one array containing the square of every element from both arrays, sorted in nondecreasing order.

Negative values are allowed. Preserve every occurrence, including duplicate values and equal squares. Either or both arrays may be empty.

Can you solve the task in O(a.length + b.length) time without sorting the squared values?

Function

mergeSortedSquares(a: int[], b: int[]) → int[]

Examples

Example 1

a = [1,3,7]b = [4,10,11]return = [1,9,16,49,100,121]

Squaring the two reported inputs gives [1,9,49] and [16,100,121]; merging gives the displayed order.

Example 2

a = [-4,-1,0,3]b = [-2,2]return = [0,1,4,4,9,16]

Both -2 and 2 contribute 4.

Example 3

a = []b = [0,5]return = [0,25]

An empty first input contributes no elements.

Constraints

  • 0 <= a.length + b.length <= 5000.
  • Both arrays are sorted in nondecreasing order.
  • -10000 <= a[i], b[i] <= 10000.

More WhatNot problems

See WhatNot hiring insights
public int[] mergeSortedSquares(int[] a, int[] b) {
    // write your code here
}
a[1,3,7]
b[4,10,11]
expected[1,9,16,49,100,121]
Checking account…