Problem 2610

(Last updated: )

Question statement:

You are given an integer array $\texttt{nums}$. You need to create a 2D array from $\texttt{nums}$ satisfying conditions below. Return the resulting array. If there are multiple answers, return any of them.

  • The 2D array should contain only the elements of the array $\texttt{nums}$.
  • Each row in the 2D array contains distinct integers.
  • The number of rows in the 2D array should be minimal.

Solution

There definitely are faster (more creative) solutions possible – but once again, this brute force solution got (somehow) accepted with a good runtime. So we will just go with this.

Main idea:

  • Collect all distinct elements of $\texttt{nums}$, this will form the first row. Once they do, delete all first instances of these elements from $\texttt{nums}$.
  • Now $\texttt{nums}$ is shorter, and repeat the same process; forming the second row and so on until $\texttt{nums}$ is empty.

If you (like me) don’t want to bother with the indexing issue, just replace all the used elements of $\texttt{nums}$ with $0$, and at each step if $0$ is encountered, $\texttt{continue}$.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def findMatrix(self, nums: List[int]) -> List[List[int]]:
    distinct = set(nums)
    twoDArray = []
    
    while distinct:
        temp = []
        for i in range(len(nums)):
            if(not distinct):
                break
            if(nums[i] == 0):
                continue
            if(nums[i] in distinct):
                temp.append(nums[i])
                distinct.remove(nums[i])
                nums[i] = 0
            else:
                continue
        twoDArray.append(temp)
        distinct = set(nums)
        distinct.remove(0)
    return twoDArray

Comments:

Time complexity: O($\texttt{len(nums)}$)

At the time of submission, the above solution passes leetcode submission cases in 35ms, beats 95.59% of users. It uses 17.4MB of memory, beating 5.13% of users.