Technical Log — LeetCode

Overview

For this week’s Spark assignment, we had to solve an algorithm problem in LeetCode. I solved two (just for fun, lol). But I’ll only explain one of them, the problem to explain is this one:

https://leetcode.com/problems/convert-an-array-into-a-2d-array-with-conditions/description/

Context

In this problem, you have the following elements:

Input: A one-dimensional array with integers that can be repeated. E.g.: [1, 3, 4, 1, 2, 3, 1].
Output: A 2-dimensional array satisfying some conditions.
Output conditions:

• The output array must have only numbers that belong to the input array.
• Each row of the output array must have different integers (no repeating numbers in a row of the array).
• The number of rows in the output array must be minimal.

Solution

To solve this problem, first you need to analyze the input, output and conditions, then, what you have is this:
As input you have a one-dimensional array ([]) and as output, you need a two-dimensional array ([[]]). This is similar to a linear transformation between vector spaces in linear algebra, we even have the conditions for the transformation.

Analyzing these conditions we must understand that,

• We can only have numbers from the original array, that is, we cannot add extra numbers or remove numbers.
• The second condition is the most important because it indicates that we can not have rows with repeated numbers, if this was not specified, we could simply create an array with a subarray that has all the numbers of the original array and this would be a bit weird.
• The last condition is also super important because it indicates that the number of rows must be minimized, that is, generate the least number of rows so that there are no repeated numbers in the same row and this is the essence of the problem. If the number of rows were not minimized, we could simply make a subarray for each number of the original array and it would fulfill the two previous conditions.

Once the problem is well defined, we proceed with the solution.

Abstracting the problem a little, we could see it in a way that the objective is to put balls of one color in boxes, in such a way that in a box there are no balls of the same color and the least amount of boxes possible is used.

Photo by Greyson Joralemon on Unsplash

So, what we do to accomplish this is:

• We fill the first box with the first ball.
• We verify that the color of the second ball is not in the first box, if it is not, we add it there, otherwise, we take a new box and put the ball there.
• Then we continue with this process, we take a ball of one color, we verify that it is not in each of the boxes, if it is not, we add it there, otherwise, we take a new box and put it there and we continue with the next ball, that is, we do not need to verify the following boxes, if there are any.

At this point we already have the solution, we only have to transfer it to an understandable algorithm for the problem and that can be passed to code, which would be as follows:

1. Create an array (box) in which the rows (boxes) will be put. This will be the array that will be returned in the output.
2. Iterate between the numbers of the input array (iterate between the balls).
3. Iterate between the output array (iterate between boxes).
4. Check if the number in that position is in this array.
5. If it is not, enter it and no longer check the following arrays (put the ball in the box and no longer check the following boxes).
6. If after checking the other arrays it is not there, add it (take a new box and put the ball there).
7. Repeat the process until there are no more numbers (balls).

And ready, this way we have a solution to this problem, with its representation using boxes and balls to make it more understandable.

Translating the solution to code in Java, it looks like this:

class Solution {
    public List<List<Integer>> findMatrix(int[] nums) {
        List<List<Integer>> rows = new ArrayList<>();
        rows.add(new ArrayList<>());

        for(int i = 0; i < nums.length; i++) {
            Boolean found = false;
            for(int j = 0; j < rows.size(); j++) {
                if(!rows.get(j).contains(nums[i])){
                    rows.get(j).add(nums[i]);
                    found = true;
                    break;
                }
            }

            if(!found){
                List<Integer> aux = new ArrayList<>();
                aux.add(nums[i]);
                rows.add(aux);
            }
        }

        return rows;
    }
}

I know that Java typing can be a little hard to understand and sometimes even ugly, but let’s ignore that for now.

So, as input we have an array of integers (int[] nums).

As output we have a List of lists of integers (This will be our box of boxes where we will put the balls).

Subsequently, we create this list of lists, to which we add an empty list, so that we can iterate over it, otherwise we would have 0 elements and we would not be able to iterate here.

Then, we iterate over the input array.

In this part we create a flag to indicate if the number was found in the subarrays in the iteration of these. If it was not found, then it is added and the other subarrays are no longer iterated, which decreases the execution time and avoids some errors such as duplicating the numbers.

After the iteration of subarrays, in case the number in question is in all the subarrays, a new one must be created to put it there. This process is repeated for all the numbers and this is how we have the corresponding output.

Alternative Solutions

Another way to solve this problem could be through HashMaps, although it would be quite similar to the essence of this way of solving it, only using HashMaps and implementing the way to manage them.