Merge Unsorted Temperature Readings — Problem Statement & Solution Guide

ArraysMediumMerge Sort / Quick Sort

TimeO(N log N)

SpaceO(N)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Merge Unsorted Temperature Readings problem optimally.

TopicArrays

PatternMerge Sort / Quick Sort

TimeO(N log N)

SpaceO(N)

Problem Description

Given two integer arrays that may be unsorted, produce a single array containing all elements from both inputs arranged in non‑decreasing order. The resulting array must include every occurrence of each value (i.e., duplicates are retained). The function should run in O(N log N) time where N is the total number of elements and may use only O(N) additional space for the output.

DSA Pattern Breakdown

"Merge Unsorted Temperature Readings"

medium

WHY DOES IT MATTER?

Sorting‑then‑merging is a foundational pattern for any problem that requires a globally ordered view of disparate data sources, ensuring predictable performance regardless of input distribution.

OPTIMIZATION CHALLENGE

Recognizing that sorting the concatenated array once is cheaper than trying to interleave unsorted streams; the insight eliminates repeated scans and yields the optimal O(N log N) bound.

REAL-WORLD CONNECTION

Think of log aggregation from multiple micro‑services: each service emits timestamps unsorted; a central collector concatenates all logs and then sorts them to reconstruct a correct chronological sequence, analogous to merging unsorted temperature readings.

In an interview, write the concatenation step explicitly, then call the built‑in sort; if asked to implement the sort, choose mergesort because its merge step naturally fits the "combine two halves" mental model and its space usage is easy to reason about.

COMPLEXITY AT A GLANCE

⏱ Time:O(N log N)

💾 Space:O(N)

Core Theory — Why This Approach?

Merging two unsorted arrays into a sorted result is a classic example of the "sort‑then‑merge" paradigm. The naïve way—concatenating the arrays and then applying a comparison‑based sort such as quicksort or mergesort—runs in O(N log N) time and uses O(N) extra space for the output, which meets the problem constraints. The key insight is that we do not need to sort each input individually; a single global sort on the combined data is sufficient because the relative order inside each original array is irrelevant. Naïve approaches that try to interleave elements without sorting (e.g., repeatedly picking the smallest remaining element by scanning both arrays) degrade to O(N^2) in the worst case, which is unacceptable for large N. By leveraging an efficient comparison‑based sort—typically mergesort or the language’s built‑in Timsort—we achieve the optimal O(N log N) time while only allocating space for the final merged array, satisfying the O(N) auxiliary space bound.

Interview Questions on This Problem

Q1How would you merge two unsorted integer arrays into a single sorted array while respecting the O(N log N) time and O(N) extra space constraints?

Concatenate the two arrays into a new list of size N, then apply a comparison‑based sort (e.g., mergesort or the language’s built‑in sort) which runs in O(N log N) time and uses O(N) auxiliary space for the output.

Q2Why is a two‑pointer linear merge unsuitable when the input arrays are unsorted?

A two‑pointer merge assumes each input is already sorted; without that guarantee the pointers cannot reliably select the next smallest element, leading to incorrect ordering or requiring a full scan for each selection, which inflates the runtime to O(N^2).

Q3Can you achieve the required complexity without using the language’s built‑in sort? If so, which algorithm would you implement and why?

Yes—implement mergesort manually. Mergesort recursively splits the combined array, sorts each half, and merges them in linear time, guaranteeing O(N log N) overall and O(N) auxiliary space for the temporary merge buffer.

Examples

Example 1

Input

nums1 = [5,1,9], nums2 = [3,7,2]

Output

[1,2,3,5,7,9]

Explanation: Combine the two lists → [5,1,9,3,7,2]. Sort them → [1,2,3,5,7,9].

Example 2

Input

nums1 = [-4,0,12,8], nums2 = [5,-4,3]

Output

[-4,-4,0,3,5,8,12]

Explanation: Merged list is [-4,0,12,8,5,-4,3]. After sorting, the order becomes [-4,-4,0,3,5,8,12].

Example 3

Input

nums1 = [100], nums2 = [100,100]

Output

[100,100,100]

Explanation: All three values are identical; after merging they remain [100,100,100] and sorting does not change the order.

Constraints

1 <= nums1.length, nums2.length <= 10^5
-10^9 <= nums1[i], nums2[i] <= 10^9
Total number of elements does not exceed 2·10^5
Expected time complexity O(N log N)
Expected auxiliary space O(N)

Optimal Approach & Strategy

Concatenate the arrays and apply a single O(N log N) comparison sort, using O(N) extra space for the result.

Brute Force Approach

Repeatedly scan both arrays to find the smallest remaining element and append it, which leads to O(N^2) time.

Code Solutions

Language:

JavaScript Solution

Time: O(N log N)

function mergeUnsortedArrays(nums1, nums2) {
    // Concatenate and sort using numeric comparator (O(N log N))
    return [...nums1, ...nums2].sort((a, b) => a - b);
}

let nums1 = [5, 1, 9];
let nums2 = [3, 7, 2];
let result = mergeUnsortedArrays(nums1, nums2);
console.log(result.join(' '));

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> mergeUnsortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
    // Combine both vectors
    nums1.insert(nums1.end(), nums2.begin(), nums2.end());
    // Sort the combined vector (O(N log N))
    std::sort(nums1.begin(), nums1.end());
    return nums1; // nums1 now holds the merged, sorted result
}

int main() {
    std::vector<int> nums1 = {5, 1, 9};
    std::vector<int> nums2 = {3, 7, 2};
    std::vector<int> result = mergeUnsortedArrays(nums1, nums2);
    for (int v : result) {
        std::cout << v << " ";
    }
    return 0;
}

import java.util.Arrays;

public class Main {
    public static int[] mergeUnsortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        int[] merged = new int[total];
        // Copy first array
        System.arraycopy(nums1, 0, merged, 0, nums1.length);
        // Copy second array
        System.arraycopy(nums2, 0, merged, nums1.length, nums2.length);
        // Sort (O(N log N))
        Arrays.sort(merged);
        return merged;
    }

    public static void main(String[] args) {
        int[] nums1 = {5, 1, 9};
        int[] nums2 = {3, 7, 2};
        int[] result = mergeUnsortedArrays(nums1, nums2);
        System.out.println(Arrays.toString(result).replaceAll("[\\[\\]]", "").replaceAll(", ", " "));
    }
}

def merge_unsorted_arrays(nums1, nums2):
    """Return a sorted list containing all elements from nums1 and nums2.
    The built‑in sorted runs in O(N log N) and uses O(N) extra space.
    """
    return sorted(nums1 + nums2)

nums1 = [5, 1, 9]
nums2 = [3, 7, 2]
result = merge_unsorted_arrays(nums1, nums2)
print(' '.join(map(str, result)))

function mergeUnsortedArrays(nums1, nums2) {
    // Concatenate and sort using numeric comparator (O(N log N))
    return [...nums1, ...nums2].sort((a, b) => a - b);
}

let nums1 = [5, 1, 9];
let nums2 = [3, 7, 2];
let result = mergeUnsortedArrays(nums1, nums2);
console.log(result.join(' '));

Asked in Top Tech Interviews

SwiggyInfosys

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.