weekly-contest-223

Welcome to Weekly Contest 223! Feel free to share and post your contest experience here!

You can also view the rankings for the contest here.

Links to the individual problems are included below:

Swapping Nodes in a Linked List (4 points)

Minimize Hamming Distance After Swap Operations (5 points)

Find Minimum Time to Finish All Jobs (6 points)

Comparing to the last 10 contests, Q1: average difficulty, 43.89% acceptance; Q2: easier than usual, 37.78% acceptance; Q3: average difficulty, 12.08% acceptance; Q4: easier than usual, 3.61% acceptance; overall: this contest is easier than usual. I compile past contest data to provide a data-driven way to assess problem difficulty. See more at:

https://docs.google.com/spreadsheets/d/14UU9Ny7ohum7JTgG1zPL0Z5IsR_qbSeLM8jNcMVfvJI/edit?usp=sharing
(Acceptance rate is calculated with caveats detailed in the spreadsheet.)

1720. Decode XORed Array

Easy

809Add to ListShare

There is a hidden integer array arr that consists of n non-negative integers.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].

You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].

Return the original array arr. It can be proved that the answer exists and is unique.

Example 1:

Input: encoded = [1,2,3], first = 1 Output: [1,0,2,1] Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

Example 2:

Input: encoded = [6,2,7,3], first = 4 Output: [4,2,0,7,4]

Constraints:

2 <= n <= 104
encoded.length == n - 1
0 <= encoded[i] <= 105
0 <= first <= 105

Since that encoded[i] = arr[i] XOR arr[i+1], then arr[i+1] = encoded[i] XOR arr[i].

Iterate on i from beginning to end, and set arr[i+1] = encoded[i] XOR arr[i].

    def decode(self, A, first):
        res = [first]
        for a in A:
            res.append(res[-1] ^ a)
        return res

    def decode(self, A, first):
        return list(accumulate([first] + A, lambda x, y: x ^ y))

1721. Swapping Nodes in a Linked List

Medium

10012Add to ListShare

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

Example 1:

Input: head = [1,2,3,4,5], k = 2 Output: [1,4,3,2,5]

Example 2:

Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5 Output: [7,9,6,6,8,7,3,0,9,5]

Example 3:

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

Example 4:

Input: head = [1,2], k = 1 Output: [2,1]

Example 5:

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

Constraints:

The number of nodes in the list is n.
1 <= k <= n <= 105
0 <= Node.val <= 100

We can transform the linked list to an array this should ease things up

After transforming the linked list to an array it becomes as easy as swapping two integers in an array then rebuilding the linked list

Solution

Overview

This is a simple problem based on the Linked List data structure. If you have solved problems using a Linked List before and have a basic idea on how a Linked List is traversed and modified, this problem will be easy to implement.

The general idea behind the problem is that we have to find the k^{th} node from the beginning and the k^{th} node from the end of the Linked List. Once we have pointers to both of these nodes, we could simply swap their values.

The problem description states that we have to swap the values of the nodes. Therefore, the actual nodes in the Linked List should remain unchanged and there is no need to change the actual list node pointers.

In this article, we're going to look at 3 different approaches. Each approach further reduces the number of passes we need to do through the list. Let's look at the approaches in detail.

Approach 1: Three Pass Approach

Intuition

Given the problem to swap 2 nodes in the linked list at k^{th} position, we need to position 2 pointers. The first pointer would point to the k^{th} node at the beginning of the list given by frontNode. The second pointer would point to the k^{th} node at the end of the list given by endNode.

Finding the position of frontNode is simple. We can start traversing from the head node until we reach the k^{th} node. But to find the endNode, we must first know the length of the Linked List. If the length of the Linked List is \text{listLength}, the k^{th} node from the end would be the \text{(listLength - k)}^{th} node.

The following figure illustrates the idea.

Algorithm

As explained above, we must implement the algorithm using 3 separate passes.

Pass 1: Find the length of the Linked List by traversing each node in the list from head node to last node and increment the counter by 1. Let the counter used to find length be listLength.

Pass 2: Traverse until the k^{th} node from the head node and set the frontNode.

Pass 3: Traverse until the listLength - k node from the head node and set the endNode.

Swap the values of frontNode and endNode using temporary variable temp.
Return the head node.

Implementation

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        int listLength = 0;
        ListNode currentNode = head;
        // find the length of linked list
        while (currentNode != null) {
            listLength++;
            currentNode = currentNode.next;
        }
        // set the front node at kth node
        ListNode frontNode = head;
        for (int i = 1; i < k; i++) {
            frontNode = frontNode.next;
        }
        //set the end node at (listLength - k)th node
        ListNode endNode = head;
        for (int i = 1; i <= listLength - k; i++) {
            endNode = endNode.next;
        }
        // swap the values of front node and end node
        int temp = frontNode.val;
        frontNode.val = endNode.val;
        endNode.val = temp;
        return head;
    }
}

Complexity Analysis

Time Complexity : \mathcal{O}(n), where n is the length of the Linked List. We are iterating over the Linked List thrice.

In the first pass, we are finding the length of the Linked List which would take \mathcal{O}(n) time.

In second pass and third pass, we are iterating k and n - k times respectively. This would take \mathcal{O}(k + n - k) i.e \mathcal{O}(n) time.

Thus, the total time complexity would be \mathcal{O}(n) + \mathcal{O}(n) = \mathcal{O}(n).
Space Complexity: \mathcal{O}(1), as we are using constant extra space to maintain list node pointers frontNode, endNode and currentNode.

Approach 2: Two Pass Approach

Approach 1 solved the problem with three passes, in O(n) time. We can't do better than O(n), because all valid solutions must count how many nodes there are in order to be able to find the k^{th} last node. But while we know we can't do better than O(n), it's still often preferable to minimize the number of loops needed for Linked List problems.

Interview Tip: Reducing the number of passes/separate loops is a very common follow-up question for Linked List problems.

The first optimization we could think of over the three pass approach is that we could find the length of the Linked List as well as the position of frontNode in a single pass.

To find the length of the Linked List we are iterating from the head node until the end of the Linked List. On the way, we would also come across the k^{th} node from the head of the list and we could set the frontNode pointer at the point.

Algorithm

The problem can be solved in two passes with the following steps:

Iterate from the head of the Linked List until the end and store the length found in listLength. In the same loop, check if we have reached the k^{th} node, and if so, set frontNode to point at that node.
Iterate from head node until listLength - k node and set the endNode.
Swap the values of frontNode and endNode using temporary variable temp.
Return the head node.

Implementation

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        int listLength = 0;
        ListNode frontNode = null;
        ListNode endNode = null;
        ListNode currentNode = head;
        // find the length of list and set the front node
        while (currentNode != null) {
            listLength++;
            if (listLength == k) {
                frontNode = currentNode;
            }
            currentNode = currentNode.next;
        }
        // set the end node at (listLength - k)th node
        endNode = head;
        for (int i = 1; i <= listLength - k; i++) {
            endNode = endNode.next;
        }
        // swap front node and end node values
        int temp = frontNode.val;
        frontNode.val = endNode.val;
        endNode.val = temp;
        return head;
    }
}

Complexity Analysis

Time Complexity : \mathcal{O}(n), where n is the length of the Linked List. We are iterating over the Linked List twice.

In the first pass, we are finding the length of the Linked List and setting the frontNode which would take \mathcal{O}(n) time.

In the second pass, we are setting the endNode by iterating n - k times.

Thus, the total time complexity would be \mathcal{O}(n) + \mathcal{O}(n - k) which is equivalent to \mathcal{O}(n).
Space Complexity: \mathcal{O}(1), as we are using constant extra space to maintain list node pointers frontNode, endNode and currentNode.

Approach 3: Single Pass Approach

Intuition

Can we implement the problem in a single pass? The problem is that to find the position of endNode we must know the length of the Linked List. And to find the length of the Linked List we must have iterated over the list before at least once.

However, we could use a trick to find the position of the pointer endNode in a single pass. The trick is:

If endNode is k positions behind a certain node currentNode, when currentNode reaches the end of linked list i.e at n^{th} node , the endNode would be at the n - k^{th} node.

A similar trick is used in a few other Linked List problems like Remove Nth Node From the End of List and the Fast and Slow Pointer Approach in Find The Middle Of Linked List.

The following figure illustrates the idea.

Let's see how we can implement this approach.

Algorithm

The problem can be implemented in a single pass using the following steps,

Start iterating from the head of the Linked List until the end using a pointer currentNode.
Keep track of the number of nodes traversed so far using the variable listLength. The listLength is incremented by 1 as each node is traversed.
If listLength is equal to k, we know that currentNode is pointing to the k^{th} node from the beginning. Set frontNode to point to the k^{th} node. Also, at this point, initialize endNode to point at the head of the linked list. Now we know that endNode is k nodes behind the head node.
If endNode is not null, we know that it is positioned k nodes behind the currentNode and so we increment endNode in addition to currentNode. When currentNode reaches the end of the list, endNode would be pointing at a node which is k nodes behind the last node.
Swap the values of frontNode and endNode using temporary variable temp.
Return the head node.

Implementation

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        int listLength = 0;
        ListNode frontNode = null;
        ListNode endNode = null;
        ListNode currentNode = head;
        // set the front node and end node in single pass
        while (currentNode != null) {
            listLength++;
            if (endNode != null)
                endNode = endNode.next;
            // check if we have reached kth node
            if (listLength == k) {
                frontNode = currentNode;
                endNode = head;
            }
            currentNode = currentNode.next;
        }
        // swap the values of front node and end node
        int temp = frontNode.val;
        frontNode.val = endNode.val;
        endNode.val = temp;
        return head;
    }
}

Complexity Analysis

Time Complexity : \mathcal{O}(n), where n is the size of Linked List. We are iterating over the entire Linked List once.
Space Complexity: \mathcal{O}(1), as we are using constant extra space to maintain list node pointers frontNode, endNode and currentNode.

1722. Minimize Hamming Distance After Swap Operations

Medium

2128Add to ListShare

You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [ai, bi] indicates that you are allowed to swap the elements at index ai and index bi (0-indexed) of array source. Note that you can swap elements at a specific pair of indices multiple times and in any order.

The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Formally, it is the number of indices i for 0 <= i <= n-1 where source[i] != target[i] (0-indexed).

Return the minimum Hamming distance of source and target after performing any amount of swap operations on array source.

Example 1:

Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]] Output: 1 Explanation: source can be transformed the following way: - Swap indices 0 and 1: source = [2,1,3,4] - Swap indices 2 and 3: source = [2,1,4,3] The Hamming distance of source and target is 1 as they differ in 1 position: index 3.

Example 2:

Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = [] Output: 2 Explanation: There are no allowed swaps. The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.

Example 3:

Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]] Output: 0

Constraints:

n == source.length == target.length
1 <= n <= 105
1 <= source[i], target[i] <= 105
0 <= allowedSwaps.length <= 105
allowedSwaps[i].length == 2
0 <= ai, bi <= n - 1
ai != bi

The source array can be imagined as a graph where each index is a node and each allowedSwaps[i] is an edge.

Nodes within the same component can be freely swapped with each other.

For each component, find the number of common elements. The elements that are not in common will contribute to the total Hamming distance.

leetcode.com/problems/minimize-hamming-distance-after-swap-operations/discuss/1009867/Python-DFS-Solution

1723. Find Minimum Time to Finish All Jobs

Hard

1376Add to ListShare

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the ith job.

There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized.

Return the minimum possible maximum working time of any assignment.

Example 1:

Input: jobs = [3,2,3], k = 3 Output: 3 Explanation: By assigning each person one job, the maximum time is 3.

Example 2:

Input: jobs = [1,2,4,7,8], k = 2 Output: 11 Explanation: Assign the jobs the following way: Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11) Worker 2: 4, 7 (working time = 4 + 7 = 11) The maximum working time is 11.

Constraints:

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 107

We can select a subset of tasks and assign it to a worker then solve the subproblem on the remaining tasks

    def minimumTimeRequired(self, A, k):
        n = len(A)
        A.sort(reverse=True) # opt 1

        def dfs(i):
            if i == n: return True # opt 3
            for j in xrange(k):
                if cap[j] >= A[i]:
                    cap[j] -= A[i]
                    if dfs(i + 1): return True
                    cap[j] += A[i]
                if cap[j] == x: break # opt 2
            return False

        # binary search
        left, right = max(A), sum(A)
        while left < right:
            x = (left + right) / 2
            cap = [x] * k
            if dfs(0):
                right = x
            else:
                left = x + 1
        return left

leetcode.com/problems/find-minimum-time-to-finish-all-jobs/discuss/1010057/Python-Binary-search-24ms