2020 June 13 Problems

[Daryl Wang]

Please work on the problems at home and post your solutions to the thread. I'll be discussing the questions in a Zoom meeting next Saturday.

690

Employee Importance

56.6%

Easy

417

Pacific Atlantic Water Flow

40.5%

Medium

472

Concatenated Words

42.7%

Hard

[Priyank Gupta]

On Saturday, June 13, 2020 at 9:06:19 AM UTC-7, Daryl Wang wrote:

Please work on the problems at home and post your solutions to the thread. I'll be discussing the questions in a Zoom meeting next Saturday.

690

Employee Importance

56.6%

Easy

Runtime: 168 ms, faster than 55.25% of Python3 online submissions for Employee Importance.

Memory Usage: 14.8 MB, less than 88.79% of Python3 online submissions for Employee Importance. 

 

#Time : O(N) N -> no of employee

#Space: O(N)

"""

# Definition for Employee.

class Employee:

    def __init__(self, id: int, importance: int, subordinates: List[int]):

        self.id = id

        self.importance = importance

        self.subordinates = subordinates

"""

class Solution:

    def buildMapping(self, employees):

        d = {}

        for emp in employees:

            d[emp.id] = emp 

        return d

    

    def dfs(self, d, id):

        if id not in d:

            return 0

        s = d[id].importance

        for subId in d[id].subordinates:

            s += self.dfs(d,subId)

        return s

            

    def getImportance(self, employees: List['Employee'], id: int) -> int:

        d = self.buildMapping(employees)

        return self.dfs(d,id)

[Priyank Gupta]

On Saturday, June 13, 2020 at 9:06:19 AM UTC-7, Daryl Wang wrote:

Please work on the problems at home and post your solutions to the thread. I'll be discussing the questions in a Zoom meeting next Saturday.

417

Pacific Atlantic Water Flow

40.5%

Medium

Runtime: 4500 ms, faster than 5.10% of Python3 online submissions for Pacific Atlantic Water Flow.

Memory Usage: 15 MB, less than 73.49% of Python3 online submissions for Pacific Atlantic Water Flow. 

 

#Time : O(mn)

#space: O(mn)

class Solution:

    def __init__(self):

        self.p = set()

        self.a = set()

    

    def dfs(self, matrix, row, col, prev, visited):

        if row < 0 or col < 0:

            self.p = self.p | visited

            return 

        if row > len(matrix)-1 or col > len(matrix[0])-1:

            self.a = self.a | visited

            return 

        if (row,col) in visited:

            return

        if prev >= matrix[row][col]:

            # if the paticular co-ord is already in any set we dont have to carry the dfs, we can just add all the paths to that set.

            if (row,col) in self.a and (row,col) in self.p:

                if (row,col) in self.a:

                    self.a = self.a | visited

                if (row,col) in self.p:

                    self.p = self.p | visited

                return

            

            visited.add((row,col))

            prev = matrix[row][col]

            

            self.dfs(matrix,row-1,col,prev,visited)

            self.dfs(matrix,row,col-1,prev,visited)

            self.dfs(matrix,row+1,col,prev,visited)

            self.dfs(matrix,row,col+1,prev,visited)

            visited.remove((row,col))

        return

            

    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:

        for row in range(len(matrix)):

            for col in range(len(matrix[0])):

                self.dfs(matrix,row,col,matrix[row][col],set())

        # at the end we have to take intersection of the atlantic and pacific sets.

        return [list(e) for e in self.p.intersection(self.a)]

                    

        

        

        

        

[rajat aggarwal]

690

Employee Importance

56.6%

Easy

public int minMoves(int[] nums) {
       
        
        if(nums.length==0 || nums.length==1)
            return 0;
       
       
        int result=0;
       
        Arrays.sort(nums);
       
        if(nums[0]== nums[nums.length-1])
        {
            return result;
        }
       
        // Calculating diff stating from last to 0+1 elemnt and updating into result.
        for(int i=nums.length-1; i>0; i--)
        {
            result+=nums[i]-nums[0];

        }            
       
        return result;
       
    }

--
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/d009c1c9-b546-4c13-84a3-01c7a1b5bb5ao%40googlegroups.com.

[Tarini Pattanaik]

690. Employee Importance

Runtime: 20 ms, faster than 5.46% of Java online submissions for Employee Importance.

  public int getImportance(List<Employee> employees, int id) {
        if (employees.size() == 0)
            return 0;
       
        Map<Integer, Employee> map = new HashMap<Integer, Employee>();
       
        Employee selctedEmp = null;
        for(Employee emp: employees) {
            map.put(emp.id, emp);
           
            if (emp.id == id) {
                selctedEmp = emp;
            }
        }
       
        System.out.println(" selected emp id " + selctedEmp.id);
       
        int sum = 0;
        if (selctedEmp != null) {
           
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.add(selctedEmp.id);
           
            while (!queue.isEmpty()) {
                int poll = queue.poll();
                selctedEmp = map.get(poll);
                System.out.println(" poll " + poll);
               
                sum += map.get(poll).importance;
                if (selctedEmp.subordinates.size() > 0) {
                    for (int child: selctedEmp.subordinates) {
                        queue.add(child);
                        System.out.println(" adding to queue " + child);
                    }
                }
            }
        }
       
        return sum;
    }

To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/CAM7qDyAa0zXnviM%2BdZAETte2NH2_4bQ-PmGmwyNhXOZdzBzC0w%40mail.gmail.com.

[karan alang]

lc 690 :

def getImportance(self, employees: List['Employee'], id: int) -> int:

        

        d = defaultdict(list)

        for e in employees:

            d[e.id] = [e.importance, e.subordinates]

        

        def rec(empId):

            

            if len(d[empId][1]) == 0:

                return d[empId][0]

            

            # subs = d[empId][1]

            impSubs = 0

            for s in d[empId][1]:

                impSubs += rec(s)

                

            return d[empId][0] + impSubs   

            

        return rec(id)    

On Saturday, June 13, 2020 at 9:06:19 AM UTC-7, Daryl Wang wrote:

[Priyank Gupta]

On Saturday, June 13, 2020 at 9:06:19 AM UTC-7, Daryl Wang wrote:

Please work on the problems at home and post your solutions to the thread. I'll be discussing the questions in a Zoom meeting next Saturday.

472

Concatenated Words

42.7%

Hard

Runtime: 420 ms, faster than 78.28% of Python3 online submissions for Concatenated Words.

Memory Usage: 17 MB, less than 83.31% of Python3 online submissions for Concatenated Words.

# This is a straight forward DFS problem, where for each word you see with how many words it is made of which exist in the wordSet.

# We can cached the looked up words key is word and val is the count of words 

# Time : O(mn) m -> max length of the word, n-> length of the words

# Space: O(m+n)

class Solution:

    def __init__(self):

        self.cache = {}

    def dfs(self, word, wordSet, start):

        if start > len(word)-1:

            return 0

        if word[start:] in self.cache:

            return self.cache[word[start:]]

        

        for i in range(start, len(word)):

            if word[start:i+1] in wordSet:

                retCount = self.dfs(word,wordSet,i+1)

                if retCount != -1:

                    self.cache[word[start:]] = retCount + 1

                    return self.cache[word[start:]]

        return -1

    

    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:

        res = []

        wordSet = set(words)

        for word in words:

            if self.dfs(word,wordSet,0) >= 2:

                res.append(word)

        return res

                

         

[Daryl Wang]

690

Employee Importance

56.6%

Easy

This is a pretty straight forward recursive problem once you have a data structure to deal with the Employee object. The target employee and the subordinates are given as ID numbers, so you'll want a mapping from ID to the employee object. Once that is set up this is a pretty basic recursive problem. Add up:

1) the importance of the target employee

2) the result of getImportance() on all of the target employee's subordinates

The recursive calls come from part 2) and will stop once we hit employees with no subordinates.

O(n) time

O(n) space

class Solution:

    def getImportance(self, employees: List['Employee'], id: int) -> int:

        employee_map = {employee.id: employee for employee in employees}

        def recursive_importance(e_id):

            employee_obj = employee_map[e_id]

            return employee_obj.importance + sum([recursive_importance(subord) for subord in employee_obj.subordinates])

        return recursive_importance(id)

On Saturday, June 13, 2020 at 9:06:19 AM UTC-7, Daryl Wang wrote:

[Daryl Wang]

417

Pacific Atlantic Water Flow

40.5%

Medium

The approach for this problem is to run two searches: one search to find all the tiles that can reach the top/left and another search to find all of the tiles that can reach the bottom/right. Each search is a bfs where the starting set of positions is the tiles along the two edges. The search keeps popping off a tile in the search list, and it adds the neighbors of the popped tile to the search list if that neighbor is equal to or higher than the popped tile in the search. Once we run out of tiles in the search list, we have found all the tiles that can reach that ocean. We do this for both oceans and then return the tiles that are in both sets.

O(m*n) space

O(m*n) time

class Solution:

    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:

        if not matrix:

            return []

        pacificAdj = set()

        atlanticAdj = set()

        for i in range(len(matrix)):

            pacificAdj.add((i, 0))

            atlanticAdj.add((i, len(matrix[0]) - 1))

        for j in range(len(matrix[0])):

            atlanticAdj.add((len(matrix) - 1, j))

            pacificAdj.add((0, j))

        def bfs(oceanSet):

            frontier = collections.deque(oceanSet, len(matrix) * len(matrix[0]))

            while frontier:

                x,y = frontier.popleft()

                neighbors = [(x+dX, y+dY) for dX, dY in [(0,1),(0,-1),(1,0),(-1,0)]

                                if 0<=x+dX<len(matrix) and 0<=y+dY<len(matrix[0])

                                and matrix[x+dX][y+dY] >= matrix[x][y]]

                for neighbor in neighbors:

                    if neighbor not in oceanSet:

                        frontier.append(neighbor)

                        oceanSet.add(neighbor)

        bfs(pacificAdj)

        bfs(atlanticAdj)

        return list(pacificAdj & atlanticAdj)

On Saturday, June 13, 2020 at 9:06:19 AM UTC-7, Daryl Wang wrote:

[Daryl Wang]

472

Concatenated Words

42.7%

Hard

The basic approach for this problem is to see if the current word starts with another word. If it does, then the problem recurs to solving the same problem for the rest of the word.

This problem can be done recursively or via dynamic programming. I've provided code below for the recursive solution. The dynamic programming approach makes an array the length of the word, and each element in the array is true if the word is a concatenation of words up to that point. A word is a concatenation is the final element of the array is true.

Strictly speaking my solution can behave badly checking the same word and offset repeatedly. In practice this only happens if words are prefixes of each other, so outside of a edge case like ["a", "aa", "aaa", "aaaa"] we're not actually repeating the same subproblem often. Memoization or the dynamic programming approach would fix this problem.

class Solution:

    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:

        # One pass to create dictionary of all words

        dictionary = set(words)

        result = []

        def isConcat(word, offset=0):

            if word == "" and not offset:

                return True

            else:                

                for i in range(len(word) - offset):

                    if word[0:i + 1] in dictionary and isConcat(word[i + 1:], offset=0):

                        return True

            return False

        result = [ word for word in words if isConcat(word, 1) ]

        return result

On Saturday, June 13, 2020 at 9:06:19 AM UTC-7, Daryl Wang wrote: