304 North Cardinal St.
Dorchester Center, MA 02124

# 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 `nums`count 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 = {}, 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 = 6, so all occurrences of the digit 9 will become 6.
2. mapping = 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;
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)
final = []
for i in n:
final.append(i)
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,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].push_back(v);
}
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, l -> new ArrayList<>()).add(e);
++inDegree[e];
}

// 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) {
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())) {
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)
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, l -> new ArrayList<>()).add(e);
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < n; ++i) {
}
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) {
}
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:
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