Arrays and Hashing. Vol.2

Aloha guys. We are going on about popular interview questions. Today we will solve a few problems with hashing approach. 

Our first problem is:

Top K Frequent Elements

Description

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Solution

So, we need to return K top elements. Based on this condition, we understand that we should calculate each element's frequency. But how can we do it? Sure let's create a hash map and calculate each element's frequency. The Key will be the element, and the value will be frequency. 

Ok, for now, we have elements frequency, but how can we get top K elements? For example, we can create our own max heap and get k elements. If you don't want to write your own heap, you can use Java PriorityQueue. When you create a priority queue, you should pass the comparator - we are going to sort by value. After it, we can poll K elements and add them to the result. Go under the hood:

Code

public int[] topKFrequent(int[] nums, int k) {
        int[] rez = new int[k];
        Map<Integer, Integer> map= new HashMap<>();

        for(int n : nums){
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a,b) -> a.getValue() - b.getValue());

        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
                pq.add(entry);
                if (pq.size() > k){
                    pq.poll();
                }
        }
        int i = k;
        while(!pq.isEmpty()){
            rez[--i] = pq.poll().getKey();

        }
        return rez;
    }

Was it clear to you guys? I hope so. 

Our next problem:

Product of Array Except Self

Description

Given an integer array nums, return an array answer such that answer[I]  is equal to the product of all the elements of nums except nums[I]. The product of any prefix or suffix of nums is guaranteed 

to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Solution

I like this problem. It changed my mind. I thought we could multiply all elements and then divide the result on the current, but unfortunately, we cannot use the division operation. 

Let's think. What will we have if we multiply elements step by step from left to right except for self?

For example [1,2,3,4]:

0. nums = [1, 2, 3, 4]
   left = [0, 0, 0, 0]
1. it is obvious that for the first element we set 1
   because we don't have items to the left and we do not include self. 
   left = [1, 0, 0, 0]
2. Then for the nex element we get prev element * prev left element
   i = 1.
   nums[i-1] * left[i-1]. left = [1, 1, 0, 0]
3. Repeat this action till the end.
4. i = 2.
   nums[i-1] * left[i-1] = 2 * 1 = 1  left = [1, 1, 2, 0]
5. i = 3
   nums[i-1] * left[i-1] = 3 * 2 = 1  left = [1, 1, 2, 6]

As a result, we have all left products in the array except for self. With the same algo, let's find all the right products.

0. nums = [1, 2, 3, 4]
   right = [0, 0, 0, 0]
1. it is obvious that for the last element we set 1
   because we don't have items to the right and we do not include self. 
   left = [0, 0, 0, 1]
2. Then for the nex element we get prev element * prev left element
   i = 1.
   nums[i-1] * left[i-1]. left = [0, 0, 4, 1]
3. Repeat this action till the end.
4. i = 2.
   nums[i-1] * left[i-1] = 4 * 3 = 12  left = [1, 12, 4, 1]
5. i = 3
   nums[i-1] * left[i-1] = 12 * 2 = 24  left = [24, 12, 4, 1]

For now, we have products left except self and right except self. We can multiply them and receive a product of the array except for self.

0. left =  [1, 1, 2, 6]
   right = [24, 12, 4, 1]
   rez =   [0, 0, 0, 0]
1. rez = [1* 24, 1 * 12, 2 * 4, 6 * 1]
2. rez = [24, 12, 8, 6]

Wow, wisdom, isn't it? 

Code

    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] toRight = new int[n];
        int[] toLeft = new int[n];
        
        toRight[0] = 1;
        toLeft[n-1] = 1;
        for(int i = 1; i < n; i++){
            toRight[i] = nums[i-1] * toRight[i-1];
        }
        for(int i = n-2; i >=0; i--){
            toLeft[i] = nums[i+1] * toLeft[i+1];
        }
        for(int i = 0; i < n; i ++){
            toRight[i] *= toLeft[i];
        }
        return toRight;
    }

Hey. have you ever tried to solve Sudoku? Our next task will help you to do it.

Valid Sudoku

Description

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain 
4. The digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Solution

Based on the description, we see three main requirements for a valid Sudoku:

• Each row must contain the digits 1-9 without repetition.

• Each column must contain the digits 1-9 without repetition.

• Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Let's try to solve this problem step by step. First of all, let's check the row of the Sudoku. We can create a Map or an array, or a Set from 1 to 10 and fill needed cells. If we see this element twice, we will return false — our Sudoku is invalid.

The same approach we will use for columns. Just check column values. 

But how can we handle squares? Looks like we have a matrix 9x9. We have nine elements in a row, nine elements in a column, and nine squares. The main problem here is to correctly determine square elements. We must find the start/end column and the start/end row. For the column, the best idea will be to get a square number (For example, 3), then multiply it by three elements in a row and then divide it by square elements count (9). 

int startRow =  (square * 3) % 9 = 3 * 3 % 9 = 1;

With the end row, all will be easier. We just need to add three lines =) 

Now, let's figure out how to calculate the start column. For square 0, it should be 0. For square 1, it also should be 0. But for square 3, it should be 3, right? Looks like we need to get a square number, divide it by 3 (because we have three columns in a square) and then multiply it by three. 

For square 0: 0 / 3 * 3 = 0;
For square 1: 1 / 3 * 3 = 0;
For square 2: 0 / 3 * 3 = 0;
For square 3: 3 / 3 * 3 = 1;
For square 6: 6 / 3 * 3 = 6;

Is it clear? 

For now, we have three base checks. And we can iterate from 1 to 9 and check 9 rows, 9 columns, and 9 squares. 

Code

public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            boolean isValidLine = isValidRow(board, i);
            boolean isValidRow = isValidColumn(board, i);
            boolean isValidSquare = isValidSquare(board, i);

            if (!isValidLine || !isValidRow || !isValidSquare) {
                return false;
            }
        }
        return true;
    }

    private boolean isValidRow(char[][] board, int line) {
        int[] dict = new int[10];
        for (int i = 0; i < board[line].length; i++) {
            char cur = board[line][i];
            if (Character.isDigit(cur)) {
                int curInt = cur - '0';
                if (curInt < 1 || curInt > 9) {
                    return false;
                }
                if (dict[curInt] > 0) {
                    return false;
                }
                dict[curInt]++;
            }
        }
        return true;
    }

    private boolean isValidColumn(char[][] board, int row) {
        int[] dict = new int[10];
        for (int i = 0; i < board.length; i++) {
            char cur = board[i][row];
            if (Character.isDigit(cur)) {
                int curInt = cur - '0';
                if (curInt < 1 || curInt > 9) {
                    return false;
                }
                if (dict[curInt] > 0) {
                    return false;
                }
                dict[curInt]++;
            }
        }
        return true;
    }

    private boolean isValidSquare(char[][] board, int square) {
        int[] dict = new int[10];

        int startRow = (square * 3) % 9;
        int endRow = startRow + 3;

        int startCol = (square / 3) * 3;
        int endCol = startCol + 3;
        for (int i = startCol; i < endCol; i++) {
            for (int j = startRow; j < endRow; j++) {
                char cur = board[i][j];
                if (Character.isDigit(cur)) {
                    int curInt = cur - '0';
                    if (curInt < 1 || curInt > 9) {
                        return false;
                    }
                    if (dict[curInt] > 0) {
                        return false;
                    }
                    dict[curInt]++;
                }
            }
        }
        return true;
    }

I know, I know a lot of code. But for now, we know how to check Sudoku. 

Longest Consecutive Sequence

Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Solution

Do you remember our topic? It is Arrays and Hashing. Let's think about how we can use it. We should find consecutive elements. For example, 1, 2, 3, 4, or maybe 10, 11, 12.  

As a brute force solution, we can try to sort an array and check all subsequences. But it will take O(NlogN) time with standard Java sort algorithms. 

Based on the base example, we understand that if we have 1 in the array, we should check 2. If we have 2 in the array, we have subsequence size two and want to check 3. Do we have it in the array? Let's try to check it, but without sorting. In this case, we need to iterate over the array N*N times. But what if we simply put all array elements into HashSet and then check them there? 

1. Put array elements into set
2. Iterate over set
3. Check element and element + 1
4. Do it till the end

But looks like this algorithm also will be N*N. It looks so, but let's check a code, and then I will try to explain.

Code

public int longestConsecutive(int[] nums) {
        int max = 0;

        Set<Integer> set = new HashSet<>();

        for (int num : nums) {
            set.add(num);
        }
        for (Integer i : set) {
            if (!set.contains(i - 1)) {
                int prev = i;
                int curMax = 1;
                while (set.contains(prev + 1)) {
                    prev++;
                    curMax++;
                }
                max = Math.max(max, curMax);
            }
        }
        return max;
    }

Although the time complexity appears to be quadratic due to the while loop nested within the for loop, closer inspection reveals it to be linear. Because the while loop is reached only when i marks the beginning of a sequence (i.e., i-1 is not present in the array), the while loop can only run for N iterations throughout the entire runtime of the algorithm. This means that despite looking like O(N*N) complexity, the nested loops actually run in O(N+N)=O(n) time. All other computations occur in constant time, so the overall runtime is linear.