Biweekly Contest 73 LeetCode Solution

Problem 1 – Most Frequent Number Following Key In an Array Leetcode Solution

You are given a 0-indexed integer array nums. You are also given an integer key, which is present in nums.

For every unique integer target in numscount the number of times target immediately follows an occurrence of key in nums. In other words, count the number of indices i such that:

  • 0 <= i <= nums.length - 2,
  • nums[i] == key and,
  • nums[i + 1] == target.

Return the target with the maximum count. The test cases will be generated such that the target with maximum count is unique.

Example 1:

Input: nums = [1,100,200,1,100], key = 1
Output: 100
Explanation: For target = 100, there are 2 occurrences at indices 1 and 4 which follow an occurrence of key.
No other integers follow an occurrence of key, so we return 100.

Example 2:

Input: nums = [2,2,2,2,3], key = 2
Output: 2
Explanation: For target = 2, there are 3 occurrences at indices 1, 2, and 3 which follow an occurrence of key.
For target = 3, there is only one occurrence at index 4 which follows an occurrence of key.
target = 2 has the maximum number of occurrences following an occurrence of key, so we return 2.

Constraints:

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • The test cases will be generated such that the answer is unique.

Most Frequent Number Following Key In an Array Leetcode Solution in C++

int mostFrequent(vector<int>& nums, int key) {
    int cnt[1001] = {}, res = 0;
    for (int i = 1; i < nums.size(); ++i)
        if (nums[i - 1] == key && ++cnt[nums[i]] > cnt[res])
            res = nums[i];
    return res;
}

Most Frequent Number Following Key In an Array Leetcode Solution in Java

    public int mostFrequent(int[] nums, int key) {
        Map<Integer, Integer> freq = new HashMap<>();
        int mostFreq = -1;
        for (int i = 0, n = nums.length, max = 0; i + 1 < n; ++i) {
            if (nums[i] == key) {
                int candidate = nums[i + 1];
                freq.put(candidate, 1 + freq.getOrDefault(candidate, 0));
                if (freq.get(candidate) > max) {
                    max = freq.get(candidate);
                    mostFreq = candidate;
                }
            }
        }
        return mostFreq;
    }

Most Frequent Number Following Key In an Array Leetcode Solution in Python

Solution – Count by hand:

class Solution:
    def mostFrequent(self, nums, key):
        counts = {}
        
        for i in range(1,len(nums)):
            if nums[i-1]==key:
                if nums[i] not in counts: counts[nums[i]] = 1
                else: counts[nums[i]] += 1
        
        return max(counts, key=counts.get)

Solution – Counter:

class Solution:
    def mostFrequent(self, nums, key):
        arr = [nums[i] for i in range(1,len(nums)) if nums[i-1]==key]
        c = Counter(arr)
        return max(c, key=c.get)

One-Liner – Counter:

class Solution:
    def mostFrequent(self, nums, key):
        return max(c := Counter([nums[i] for i in range(1,len(nums)) if nums[i-1]==key]), key=c.get)

One-Liner – Mode:

class Solution:
    def mostFrequent(self, nums, key):
        return mode(nums[i] for i in range(1,len(nums)) if nums[i-1]==key)

One-Liner – Mode with Pairwise

class Solution:
    def mostFrequent(self, nums, key):
        return mode(b for a, b in pairwise(nums) if a == key)

Problem 2 – Sort the Jumbled Numbers Leetcode Solution

You are given a 0-indexed integer array mapping which represents the mapping rule of a shuffled decimal system. mapping[i] = j means digit i should be mapped to digit j in this system.

The mapped value of an integer is the new integer obtained by replacing each occurrence of digit i in the integer with mapping[i] for all 0 <= i <= 9.

You are also given another integer array nums. Return the array nums sorted in non-decreasing order based on the mapped values of its elements.

Notes:

  • Elements with the same mapped values should appear in the same relative order as in the input.
  • The elements of nums should only be sorted based on their mapped values and not be replaced by them.

Example 1:

Input: mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]
Output: [338,38,991]
Explanation: 
Map the number 991 as follows:
1. mapping[9] = 6, so all occurrences of the digit 9 will become 6.
2. mapping[1] = 9, so all occurrences of the digit 1 will become 9.
Therefore, the mapped value of 991 is 669.
338 maps to 007, or 7 after removing the leading zeros.
38 maps to 07, which is also 7 after removing leading zeros.
Since 338 and 38 share the same mapped value, they should remain in the same relative order, so 338 comes before 38.
Thus, the sorted array is [338,38,991].

Example 2:

Input: mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]
Output: [123,456,789]
Explanation: 789 maps to 789, 456 maps to 456, and 123 maps to 123. Thus, the sorted array is [123,456,789].

Constraints:

  • mapping.length == 10
  • 0 <= mapping[i] <= 9
  • All the values of mapping[i] are unique.
  • 1 <= nums.length <= 3 * 104
  • 0 <= nums[i] < 109

Sort the Jumbled Numbers Leetcode Solution in Java

    public int[] sortJumbled(int[] mapping, int[] nums) {
        int n = nums.length, k = 0;
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; ++i)
            indices[i] = i;
        Arrays.sort(indices, Comparator.comparing(i -> convert(nums[i], mapping)));
     // return Stream.of(indices).mapToInt(i -> nums[i]).toArray();
        int[] ans = new int[n];
        for (int idx : indices)
            ans[k++] = nums[idx];
        return ans;
    }
    private int convert(int num, int[] mapping) {
        if (num == 0)
            return mapping[0];
        int n = 0, f = 1;
        while (num > 0) {
            n += mapping[num % 10] * f;
            f *= 10;
            num /= 10;
        }
        return n;
    }

Sort the Jumbled Numbers Leetcode Solution in C++

class Solution {
public:
    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {   
        vector<pair<int,int>>vec;
        
        for(int i = 0;i<nums.size();++i){
            int num = nums[i];
          string number = to_string(num); 
            string formed = "";
          for(int j= 0;j<number.size();++j){
              formed+=(to_string(mapping[number[j]-'0']));
          }
          int value = stoi(formed);
          vec.push_back({value,i});
        }
        
        sort(vec.begin(),vec.end());
        vector<int>ans;
        for(auto pa:vec){
            int found = nums[pa.second];
            ans.push_back(found);
        }
        
        return ans;
    }
};

Sort the Jumbled Numbers Leetcode Solution in Python

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        n = []
        for i in nums:
            s = ""
            l = list(str(i))
            for j in l:
                s += str(mapping[int(j)])
            n.append([i, int(s)])
        n.sort(key=lambda x: x[1])
        final = []
        for i in n:
            final.append(i[0])
        return final

Problem 3 – All Ancestors of a Node in a Directed Acyclic Graph Leetcode Solution

You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph.

Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

Example 1:

Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.

Example 2:

Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Node 0 does not have any ancestor.
- Node 1 has one ancestor 0.
- Node 2 has two ancestors 0 and 1.
- Node 3 has three ancestors 0, 1, and 2.
- Node 4 has four ancestors 0, 1, 2, and 3.

Constraints:

  • 1 <= n <= 1000
  • 0 <= edges.length <= min(2000, n * (n - 1) / 2)
  • edges[i].length == 2
  • 0 <= fromi, toi <= n - 1
  • fromi != toi
  • There are no duplicate edges.
  • The graph is directed and acyclic.

All Ancestors of a Node in a Directed Acyclic Graph Leetcode Solution in C++

class Solution {
public:
    void dfs(vector<vector<int>> &graph,int i,int j,vector<vector<int>> &ans){
        for(auto &x:graph[j]){
            if(ans[x].empty() || ans[x].back()!=i){
                ans[x].push_back(i);
                dfs(graph,i,x,ans);
            }
        }
    }
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<vector<int>> ans(n),graph(n);
        for(auto &v:edges){
            graph[v[0]].push_back(v[1]);
        }
        for(int i=0;i<n;i++){
            dfs(graph,i,i,ans);
        }
        return ans;
    }
};

All Ancestors of a Node in a Directed Acyclic Graph Leetcode Solution in Java

Topological Sort

    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        
        // Build graph, and compute in degree.
        int[] inDegree = new int[n];
        Map<Integer, List<Integer>> parentToKids = new HashMap<>();
        for (int[] e : edges) {
            parentToKids.computeIfAbsent(e[0], l -> new ArrayList<>()).add(e[1]);
            ++inDegree[e[1]];
        }
        
        // 1. Use a list of sets to save ancestors 
        // and to avoid duplicates.
        // 2. Use a Queue to save 0-in-degree nodes as
        // the starting nodes for topological sort.
        List<Set<Integer>> sets = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            sets.add(new HashSet<>());
            if (inDegree[i] == 0)
                q.offer(i);
        }
        
        // BFS to their neighbors and decrease 
        // the in degrees, when reaching 0, add
        // it into queue;
        // During this procedure, get direct parent, add 
        // all ancestors of direct parents' of each kid.
        while (!q.isEmpty()) {
            int parent = q.poll();
            for (int kid : parentToKids.getOrDefault(parent, Arrays.asList())) {
                sets.get(kid).add(parent);
                sets.get(kid).addAll(sets.get(parent));
                if (--inDegree[kid] == 0)
                    q.offer(kid);
            }
        }
        
        // Sort ancestors and put into return list. 
        List<List<Integer>> ans = new ArrayList<>();
        for (Set<Integer> set : sets)
            ans.add(new ArrayList<>(new TreeSet<>(set)));
        return ans;
    }

DFS

    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        Map<Integer, List<Integer>> parentToKids = new HashMap<>();
        for (int[] e : edges) {
            parentToKids.computeIfAbsent(e[0], l -> new ArrayList<>()).add(e[1]);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            ans.add(new ArrayList<>());
        }
        for (int i = 0; i < n; ++i) {
            dfs(i, i, ans, parentToKids);
        }
        return ans;
    }
    private void dfs(int ancestor, int kid, List<List<Integer>> ans, Map<Integer, List<Integer>> parentToKids) {
        List<Integer> ancestors = ans.get(kid);
        if (ancestors.isEmpty() || ancestors.get(ancestors.size() - 1) != ancestor) {
            if (ancestor != kid) {
                ancestors.add(ancestor);
            }
            for (int grandKid : parentToKids.getOrDefault(kid, Arrays.asList())) {
                dfs(ancestor, grandKid, ans, parentToKids);
            }
        }
    }

All Ancestors of a Node in a Directed Acyclic Graph Leetcode Solution in Python

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        graph = {}
        for a, b in edges:
            graph[b] = graph.get(b, []) + [a]
        op = [[] for i in range(n)]
        for a in graph:
            visited = set()
            paths = [a]
            while len(paths) > 0:
                curr = paths.pop()
                for b in graph.get(curr, []):
                    if b not in visited:
                        visited.add(b)
                        paths.append(b)
            op[a] = sorted(visited)
        return op

Problem 4 – Minimum Number of Moves to Make Palindrome Leetcode Solution

You are given a string s consisting only of lowercase English letters.

In one move, you can select any two adjacent characters of s and swap them.

Return the minimum number of moves needed to make s a palindrome.

Note that the input will be generated such that s can always be converted to a palindrome.

Example 1:

Input: s = "aabb"
Output: 2
Explanation:
We can obtain two palindromes from s, "abba" and "baab". 
- We can obtain "abba" from s in 2 moves: "aabb" -> "abab" -> "abba".
- We can obtain "baab" from s in 2 moves: "aabb" -> "abab" -> "baab".
Thus, the minimum number of moves needed to make s a palindrome is 2.

Example 2:

Input: s = "letelt"
Output: 2
Explanation:
One of the palindromes we can obtain from s in 2 moves is "lettel".
One of the ways we can obtain it is "letelt" -> "letetl" -> "lettel".
Other palindromes such as "tleelt" can also be obtained in 2 moves.
It can be shown that it is not possible to obtain a palindrome in less than 2 moves.

Constraints:

  • 1 <= s.length <= 2000
  • s consists only of lowercase English letters.
  • s can be converted to a palindrome using a finite number of moves.

Minimum Number of Moves to Make Palindrome Leetcode Solution in C++

    int minMovesToMakePalindrome(string s) {
        int res = 0;
        while (s.size()) {   
            int i = s.find(s.back());
            if (i == s.size() - 1)
                res += i / 2;
            else
                res += i, s.erase(i, 1);
            s.pop_back();
        }
        return res; 
    }

Minimum Number of Moves to Make Palindrome Leetcode Solution in Python

    def minMovesToMakePalindrome(self, s):
        s = list(s)
        res = 0
        while s:
            i = s.index(s[-1])
            if i == len(s) - 1:
                res += i / 2
            else:
                res += i
                s.pop(i)
            s.pop()
        return res

Minimum Number of Moves to Make Palindrome Leetcode Solution in Java

class Solution {

	public int minMovesToMakePalindrome(String s) {
		int len = s.length();
		char[] strArr = s.toCharArray();        
		int steps = 0;
		int l = 0, r = len-1;                                           // use two pointers l for left and r for right. 

		while(l < r){            
			if(strArr[l] == strArr[r]){                                 // Both characters are equal. so keep going futher.
				l++; r--;
			}else{                                                      // Both characters are not equal.    
				int k = r;
				k = findKthIndexMatchingwithLthIndex(strArr, l, k);     // loop through k, until char at index k = char at index l              

				if(k == l){                                             // we did not find any char at k = char at index l    
					swap(strArr, l);
					steps++;   
				}else{                                                  
					while(k < r){                                           
						swap(strArr, k);
						steps++;
						k++;
					}
					l++; r--;
				}                
			}// end of else

		}   // end of while
		System.out.println("palindrome: "+String.valueOf(strArr));
		return steps;

	}

	public int findKthIndexMatchingwithLthIndex(char[] strArr, int l, int k){
		while(k > l){
			if(strArr[k] == strArr[l]){  return k;  }                    
			k--;
		}
		return k;
	}

	public void swap(char[] strArr, int l){
		if(l+1 < strArr.length){
			char tempCh = strArr[l];
			strArr[l] = strArr[l+1];
			strArr[l+1] = tempCh;
		}
	}
}
Biweekly Contest 73 LeetCode Solution Review:

In our experience, we suggest you solve this Biweekly Contest 73 LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Biweekly Contest 73 LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Biweekly Contest 73 LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.