We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Convert an Array Into a 2D Array With Conditions

Number: 2724

Difficulty: Medium

Paid? No

Companies: Amazon, Uber, Apple, Adobe

Problem Description

Given an integer array nums, construct a 2D array using only the elements from nums such that:

  • Every row contains distinct integers.
  • The total number of rows is minimal. You can return any valid 2D array meeting these conditions, and rows can have differing lengths.

Key Insights

  • The minimal number of rows is determined by the maximum frequency of any element in nums.
  • Each occurrence of a number is placed in a different row to ensure distinctness within rows.
  • Use a frequency counter to determine how many rows are needed.
  • For each row, include all numbers that still have remaining occurrences.

Space and Time Complexity

Time Complexity: O(n) – We traverse nums to build a frequency map and then iterate over the unique elements for the number of rows, bounded by O(n). Space Complexity: O(n) – Additional space is used for the frequency map and the resulting 2D array.

Solution

The approach begins by counting the frequency of each element in nums. The maximum frequency among elements determines the minimal number of rows required. For each row (from 0 to maximum frequency - 1), iterate over the unique numbers and add the number to the row if its frequency is at least the current row index + 1. This ensures that each row gets only one occurrence of each number, thus keeping the row distinct, and all occurrences across rows are accounted for.

Code Solutions

# Python solution
from collections import Counter

def findMatrix(nums):
    # Count the frequency of each number
    freq = Counter(nums)
    # The number of rows needed is the maximum frequency
    rows = [[] for _ in range(max(freq.values()))]
    # For each unique number, append it to as many rows as its frequency
    for num, count in freq.items():
        for i in range(count):
            rows[i].append(num)
    return rows

# Example usage:
# nums = [1,3,4,1,2,3,1]
# print(findMatrix(nums))
← Back to All Questions