2020 October 10 Questions (Roll over from last week)

[Daryl Wang]

A reminder that this week's problems are being rolled over from last week, since we didn't have any submissions. We worked through two solutions to the Keys and Rooms problem as a group, so please try to implement that. I'll be discussing the last 2 problems on https://us04web.zoom.us/j/75935635058?pwd=TjFPaitDOEN3YzVtbkt0K200T1huZz09 next Saturday.

841

Keys and Rooms

64.7%

Medium

1361

Validate Binary Tree Nodes

46.1%

Medium

765

Couples Holding Hands

54.7%

Hard

[safique ahemad]

841

Keys and Rooms

64.7%

Medium

var recUnlock func(room int)
func canVisitAllRooms(rooms [][]int) bool {
    sum := 0
    N := len(rooms)
    doorOpen := make([]bool, N)
   
    recUnlock = func(room int) {
       
        for _, k := range rooms[room] {
            if k < N && (room != k && doorOpen[k] == false) {
                sum += k
                doorOpen[k] = true
                rec(k)
            }
        }
    }
   
    recUnlock(0)
   
    actualSum := (N * (N-1))/2
   
    return sum == actualSum
}

--
Jan 2020 : 4 FAANG OFFERS. 2019: 15 FAANG OFFERS
 
https://www.techbayarea.us/
 
FB: https://www.facebook.com/techbayarea.us
Discord: https://discord.gg/yWMWptS
meetup : https://www.meetup.com/techbayarea/
google groups: https://groups.google.com/forum/#!forum/leetcode-meetup
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/6520cbb9-e690-4b3a-a70b-5d739cddf9aao%40googlegroups.com.

--

Regards,

Safique Ahemad

[Daryl Wang]

841

Keys and Rooms

64.7%

Medium

Ultimately this is just a graph search problem. Start with the first room, and add all of the keys there to the queue of rooms to explore next. Each time you visit a room add the keys there to the queue of further rooms to explore. This problem is pretty straightforward. The only noteworthy caveat is to not waste time revisiting rooms.

O(rooms) time

O(rooms) space

class Solution:

    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:

        visited = set()

        unlocked = [0]

        while unlocked:

            nextRoom = unlocked.pop()

            visited.add(nextRoom)

            keys = rooms[nextRoom]

            unlocked += [ key for key in keys if key not in visited ]

        return len(visited) == len(rooms)

[Daryl Wang]

1361Validate Binary Tree Nodes46.1%Medium

The main trick to this problem is that you can figure out who the parent of a node is by looking at the leftChild and rightChild arrays. For each leftChild[i], we know that i is the parent of leftChild[i]. Same for the right child. We can iterate through the child arrays and build a map of which parents a node has. Most nodes should have only one parent, but there should be exactly one node with no parents: the root node. If there are multiple nodes with no parents, then we know immediately that the graph isn't a tree. This check is good enough for a lot of cases, but there are some edge cases it misses, such as the case of one isolated node and a circle of nodes.

Once we know the root, we can do a dfs from the root, and check if every node is reachable from the node. The graph is a tree only if every node is seen during the dfs.

O(n) time

O(n) space

class Solution:

    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:

        parent = collections.defaultdict(set)

        for i, child in enumerate(leftChild):

            parent[child].add(i)

        for i, child in enumerate(rightChild):

            parent[child].add(i)

        root = -1

        for node in range(n):

            parents = parent[node]

            if len(parents) == 1:

                continue

            elif len(parents) == 0:

                if root < 0:

                    root = node

                else:

                    return False

            else:

                return False

        visited = set()

        def dfs(node):

            if node >= 0:

                visited.add(node)

                dfs(leftChild[node])

                dfs(rightChild[node])

        dfs(root)

        return len(visited) == n

On Saturday, October 10, 2020 at 10:47:46 AM UTC-7, Daryl Wang wrote:

[Daryl Wang]

765

Couples Holding Hands

54.7%

Hard

This problem is tricky conceptually. Ultimately it is a permutation graph problem. We define the nodes of the graph as two adjacent seats, so the first node is the two people sitting at 0 and 1, the second node is the two people sitting at 2 and 3, etc. We draw a edge between two nodes if one part of a couple is one node and the other partner is in the other node. This way a couple already sitting next to each other form a node whose only edge points to itself. A couple that has been split apart will be in two separate nodes, with the nodes connected by an edge. At this point we'll have a bunch of isolated nodes, and a bunch of cycles. The isolated nodes are couples that are already sitting next to each other. The cycles are couples that need to be swapped into place, so each cycle of k nodes will require k - 1 swaps.

This gives us the overall algorithm: create a graph out of the couples, and then use union-find to find the connected components of the graph. Once we have the components, we can count the number of swaps by sum(size of each component - 1). Alternatively, we can keep track of the number of union operations, since each union represents a swap that needs to be made.

O(n) time (Union-find is linear time for all practical purposes)

O(n) space

class Solution:

    def minSwapsCouples(self, row: List[int]) -> int:

        couches = {}

        self.swaps = len(row) / 2

        parents = {}

        sizes = {}

        def find(A):

            if parents[A] != A:

                parents[A] = find(parents[A])

            return parents[A]

        def union(A, B):

            parent1 = find(A)

            parent2 = find(B)

            if parent1 == parent2:

                return

            if sizes[parent1] < sizes[parent2]:

                parent1, parent2 = parent2, parent1

            parents[parent2] = parent1

            if sizes[parent1] == sizes[parent2]:

                sizes[parent1] += 1

            self.swaps -= 1

            

        for couch in range(len(row) // 2):

            parents[couch] = couch

            sizes[couch] = 1

        for couch in range(len(row) // 2):

            a = row[couch * 2]

            b = row[couch * 2 + 1]

            union(a // 2, b // 2)

        return int(len(row) / 2 - self.swaps)

On Saturday, October 10, 2020 at 10:47:46 AM UTC-7, Daryl Wang wrote: