304 North Cardinal St.
Dorchester Center, MA 02124

# Weekly Contest 284 LeetCode Solution

## Problem 1 – Find All K-Distant Indices in an Array Leetcode Solution

You are given a 0-indexed integer array `nums` and two integers `key` and `k`. A k-distant index is an index `i` of `nums` for which there exists at least one index `j` such that `|i - j| <= k` and `nums[j] == key`.

Return a list of all k-distant indices sorted in increasing order.

Example 1:

``````Input: nums = [3,4,9,1,3,9,5], key = 9, k = 1
Output: [1,2,3,4,5,6]
Explanation: Here, nums == key and nums == key.
- For index 0, |0 - 2| > k and |0 - 5| > k, so there is no j where |0 - j| <= k and nums[j] == key. Thus, 0 is not a k-distant index.
- For index 1, |1 - 2| <= k and nums == key, so 1 is a k-distant index.
- For index 2, |2 - 2| <= k and nums == key, so 2 is a k-distant index.
- For index 3, |3 - 2| <= k and nums == key, so 3 is a k-distant index.
- For index 4, |4 - 5| <= k and nums == key, so 4 is a k-distant index.
- For index 5, |5 - 5| <= k and nums == key, so 5 is a k-distant index.
- For index 6, |6 - 5| <= k and nums == key, so 6 is a k-distant index.
Thus, we return [1,2,3,4,5,6] which is sorted in increasing order.
``````

Example 2:

``````Input: nums = [2,2,2,2,2], key = 2, k = 2
Output: [0,1,2,3,4]
Explanation: For all indices i in nums, there exists some index j such that |i - j| <= k and nums[j] == key, so every index is a k-distant index.
Hence, we return [0,1,2,3,4].
``````

Constraints:

• `1 <= nums.length <= 1000`
• `1 <= nums[i] <= 1000`
• `key` is an integer from the array `nums`.
• `1 <= k <= nums.length`

### Find All K-Distant Indices in an Array Leetcode Solution in C++

``````vector<int> findKDistantIndices(vector<int>& nums, int key, int k) {
vector<int> res;
for (int i = 0, j = 0; i < nums.size(); ++i)
if (nums[i] == key)
for (j = max(j, i - k); j <= i + k && j < nums.size(); ++j)
res.push_back(j);
return res;
}
``````

### Find All K-Distant Indices in an Array Leetcode Solution in Java

``````public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
List<Integer> idx = new ArrayList<>();
List<Integer> ans = new ArrayList<>();
for(int i = 0 ; i < nums.length; i++){
if(nums[i] == key){
}
}
int last = 0;
for(int ind : idx){
int i = Math.max(last,ind-k);
for(; i <= ind+k && i < nums.length; i++){
}
last = i;
}
return ans;
}
``````

### Find All K-Distant Indices in an Array Leetcode Solution in Python

``````class Solution:
def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
lis=deque([])
prev_popped=-1
for i in range(len(nums)):
if(nums[i]==key):
lis.append(i)
ans=[]
for i in range(len(nums)):
if(len(lis)>0 and lis<i):
prev_popped = lis.popleft()
if(prev_popped!=-1 and (i-prev_popped) <=k):
ans.append(i)
elif(len(lis)>0 and (lis-i)<=k):
ans.append(i)
return ans
``````

## Problem 2 – Count Artifacts That Can Be Extracted Leetcode Solution

There is an `n x n` 0-indexed grid with some artifacts buried in it. You are given the integer `n` and a 0-indexed 2D integer array `artifacts` describing the positions of the rectangular artifacts where `artifacts[i] = [r1i, c1i, r2i, c2i]` denotes that the `ith` artifact is buried in the subgrid where:

• `(r1i, c1i)` is the coordinate of the top-left cell of the `ith` artifact and
• `(r2i, c2i)` is the coordinate of the bottom-right cell of the `ith` artifact.

You will excavate some cells of the grid and remove all the mud from them. If the cell has a part of an artifact buried underneath, it will be uncovered. If all the parts of an artifact are uncovered, you can extract it.

Given a 0-indexed 2D integer array `dig` where `dig[i] = [ri, ci]` indicates that you will excavate the cell `(ri, ci)`, return the number of artifacts that you can extract.

The test cases are generated such that:

• No two artifacts overlap.
• Each artifact only covers at most `4` cells.
• The entries of `dig` are unique.

Example 1:

``````Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]
Output: 1
Explanation:
The different colors represent different artifacts. Excavated cells are labeled with a 'D' in the grid.
There is 1 artifact that can be extracted, namely the red artifact.
The blue artifact has one part in cell (1,1) which remains uncovered, so we cannot extract it.
Thus, we return 1.
``````

Example 2:

``````Input: n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]]
Output: 2
Explanation: Both the red and blue artifacts have all parts uncovered (labeled with a 'D') and can be extracted, so we return 2.
``````

Constraints:

• `1 <= n <= 1000`
• `1 <= artifacts.length, dig.length <= min(n2, 105)`
• `artifacts[i].length == 4`
• `dig[i].length == 2`
• `0 <= r1i, c1i, r2i, c2i, ri, ci <= n - 1`
• `r1i <= r2i`
• `c1i <= c2i`
• No two artifacts will overlap.
• The number of cells covered by an artifact is at most `4`.
• The entries of `dig` are unique.

### Count Artifacts That Can Be Extracted Leetcode Solution in Java

``````class Solution {
public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
HashSet<String> set = new HashSet<>();
for (int d[] : dig) set.add(d + " " + d);
int c = 0;
for (int a[] : artifacts) {
boolean done = true;
for (int i = a; i <= a; i++) {
for (int j = a; j <= a; j++) {
if (!set.contains(i + " " + j)) done = false;
}
}
if (done) c++;
}
return c;
}
}
//TC = O(DIG + N^2)
``````

### Count Artifacts That Can Be Extracted Leetcode Solution in C++

``````class Solution {
public:
int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
vector<vector<bool>>visited(n,vector<bool>(n,0));
for(auto vec:dig){
visited[vec][vec] = 1;
}

int count = 0;
for(auto artifact:artifacts){
int r1 = artifact;
int c1 = artifact;
int r2 = artifact;
int c2 = artifact;
bool flag = true;

for(int i = r1;i<=r2;i++){
for(int j = c1;j<=c2;j++){
if(!visited[i][j]){
flag = false;
}
}
}

if(flag)
count++;
}

return count;
}
};
Time Complexity: O(n^2)
Space Complexity: O(n^2)
``````

### Count Artifacts That Can Be Extracted Leetcode Solution in Python

``````class Solution:
def digArtifacts(self, n: int, artifacts: List[List[int]], dig: List[List[int]]) -> int:
s=set()
for i in dig:
ans=0
for a in artifacts:
flag=0
for i in range(a,a+1):
for j in range(a,a+1):
if((i,j) not in s):
flag=1
break
if(flag==0):ans+=1
return ans
``````

## Problem 3 – Maximize the Topmost Element After K Moves Leetcode Solution

You are given a 0-indexed integer array `nums` representing the contents of a pile, where `nums` is the topmost element of the pile.

In one move, you can perform either of the following:

• If the pile is not empty, remove the topmost element of the pile.
• If there are one or more removed elements, add any one of them back onto the pile. This element becomes the new topmost element.

You are also given an integer `k`, which denotes the total number of moves to be made.

Return the maximum value of the topmost element of the pile possible after exactly `k` moves. In case it is not possible to obtain a non-empty pile after `k` moves, return `-1`.

Example 1:

``````Input: nums = [5,2,2,4,0,6], k = 4
Output: 5
Explanation:
One of the ways we can end with 5 at the top of the pile after 4 moves is as follows:
- Step 1: Remove the topmost element = 5. The pile becomes [2,2,4,0,6].
- Step 2: Remove the topmost element = 2. The pile becomes [2,4,0,6].
- Step 3: Remove the topmost element = 2. The pile becomes [4,0,6].
- Step 4: Add 5 back onto the pile. The pile becomes [5,4,0,6].
Note that this is not the only way to end with 5 at the top of the pile. It can be shown that 5 is the largest answer possible after 4 moves.
``````

Example 2:

``````Input: nums = , k = 1
Output: -1
Explanation:
In the first move, our only option is to pop the topmost element of the pile.
Since it is not possible to obtain a non-empty pile after one move, we return -1.
``````

Constraints:

• `1 <= nums.length <= 105`
• `0 <= nums[i], k <= 109`

### Maximize the Topmost Element After K Moves Leetcode Solution in Python

``````    def maximumTop(self, nums: List[int], k: int) -> int:
if (len(nums) == 1) and (k & 1): return -1

maxi = -1
for i in range(min(len(nums), k-1)):
maxi = max(maxi, nums[i])

if k < len(nums):
maxi = max(maxi, nums[k])

return maxi

``````

### Maximize the Topmost Element After K Moves Leetcode Solution in Java

``````public static int maximumTop(int[] nums, int k) {
if (nums.length == 1 && k % 2 == 1) return -1; // if size is 1 and k odd stack will be empty
int max = 0;
for (int i = 0; i < Math.min(k - 1 ,nums.length); i++) //finding the max element from first k-1 elelment or len -1 if len is less than k
max = Math.max(max, nums[i]);
if (k < nums.length)  // check for scenario where we dont have to put back Max out of k-1 element
max = Math.max(max, nums[k]);
return max;
}
``````

### Maximize the Topmost Element After K Moves Leetcode Solution in C++

``````class Solution {
public:
int maximumTop(vector<int>& v, int k) {
int n=v.size();
if(n==1 && k%2==1){
return -1;
}
int mx=INT_MIN;
for(int i=0;i<n && i<k-1;i++){
mx=max(mx,v[i]);
}
if(k<n){
mx=max(mx,v[k]);
}
return mx;
}
};
``````

### Maximize the Topmost Element After K Moves Leetcode Solution in Python 3

``````class Solution:
def maximumTop(self, nums: List[int], k: int) -> int:
if len(nums) == 1:
if k%2 != 0:
return -1
return nums

if k == 0:
return nums
if k == len(nums):
return max(nums[:-1])
if k > len(nums):
return max(nums)
if k == 1:
return nums
m = max(nums[:k-1])
m = max(m, nums[k])
return m
``````

## Problem 4 – Minimum Weighted Subgraph With the Required Paths Leetcode Solution

You are given an integer `n` denoting the number of nodes of a weighted directed graph. The nodes are numbered from `0` to `n - 1`.

You are also given a 2D integer array `edges` where `edges[i] = [fromi, toi, weighti]` denotes that there exists a directed edge from `fromi` to `toi` with weight `weighti`.

Lastly, you are given three distinct integers `src1``src2`, and `dest` denoting three distinct nodes of the graph.

Return the minimum weight of a subgraph of the graph such that it is possible to reach `dest` from both `src1` and `src2` via a set of edges of this subgraph. In case such a subgraph does not exist, return `-1`.

subgraph is a graph whose vertices and edges are subsets of the original graph. The weight of a subgraph is the sum of weights of its constituent edges.

Example 1:

``````Input: n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5
Output: 9
Explanation:
The above figure represents the input graph.
The blue edges represent one of the subgraphs that yield the optimal answer.
Note that the subgraph [[1,0,3],[0,5,6]] also yields the optimal answer. It is not possible to get a subgraph with less weight satisfying all the constraints.
``````

Example 2:

``````Input: n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
Output: -1
Explanation:
The above figure represents the input graph.
It can be seen that there does not exist any path from node 1 to node 2, hence there are no subgraphs satisfying all the constraints.
``````

Constraints:

• `3 <= n <= 105`
• `0 <= edges.length <= 105`
• `edges[i].length == 3`
• `0 <= fromi, toi, src1, src2, dest <= n - 1`
• `fromi != toi`
• `src1``src2`, and `dest` are pairwise distinct.
• `1 <= weight[i] <= 105`

### Minimum Weighted Subgraph With the Required Paths Leetcode Solution in Python

``````class Solution:
def minimumWeight(self, n, edges, s1, s2, dest):
G1 = defaultdict(list)
G2 = defaultdict(list)
for a, b, w in edges:
G1[a].append((b, w))
G2[b].append((a, w))

def Dijkstra(graph, K):
q, t = [(0, K)], {}
while q:
time, node = heappop(q)
if node not in t:
t[node] = time
for v, w in graph[node]:
heappush(q, (time + w, v))
return [t.get(i, float("inf")) for i in range(n)]

arr1 = Dijkstra(G1, s1)
arr2 = Dijkstra(G1, s2)
arr3 = Dijkstra(G2, dest)

ans = float("inf")
for i in range(n):
ans = min(ans, arr1[i] + arr2[i] + arr3[i])

return ans if ans != float("inf") else -1
``````

### Minimum Weighted Subgraph With the Required Paths Leetcode Solution in C++

``````void bfs(int st, vector<vector<pair<int, int>>> &al, vector<long long>& visited) {
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.push({0, st});
while (!pq.empty()) {
auto [dist, i] = pq.top(); pq.pop();
if (visited[i] != dist)
continue;
for (auto [j, w] : al[i]) {
if (visited[j] > dist + w) {
visited[j] = dist + w;
pq.push({visited[j], j});
}
}
}
}
long long minimumWeight(int n, vector<vector<int>>& edges, int src1, int src2, int dest) {
long long max_val = 10000000000, res = LLONG_MAX;
vector<vector<pair<int, int>>> al(n), ral(n);
vector<long long> dd(n, max_val), s1d(n, max_val), s2d(n, max_val);
dd[dest] = s1d[src1] = s2d[src2] = 0;
for (auto &e : edges) {
al[e].push_back({e, e});
ral[e].push_back({e, e});
}
bfs(dest, ral, dd);
bfs(src1, al, s1d);
bfs(src2, al, s2d);
if (dd[src1] == max_val || dd[src2] == max_val)
return -1;
for (int i = 0; i < n; ++i)
res = min(res, dd[i] + s1d[i] + s2d[i]);
return res;
}
``````

### Minimum Weighted Subgraph With the Required Paths Leetcode Solution in Java

``````class Solution {
ArrayList<int[]>[] nextGraph, preGraph;

public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
buildGraph(n, edges);

long[] src1To = new long[n], src2To = new long[n], toDest = new long[n];
Arrays.fill(src1To, -1);
Arrays.fill(src2To, -1);
Arrays.fill(toDest, -1);

shortestPath(src1, src1To, nextGraph);
shortestPath(src2, src2To, nextGraph);
shortestPath(dest, toDest, preGraph);

long res = -1;
for (int i = 0; i < n; i++) {
long d1 = src1To[i], d2 = src2To[i], d3 = toDest[i];
if (d1 >= 0 && d2 >= 0 && d3 >= 0) {
long d = d1 + d2 + d3;
if (res == -1 || d < res) {
res = d;
}
}
}

return res;
}

private void buildGraph(int n, int[][] edges) {
nextGraph = new ArrayList[n];
preGraph = new ArrayList[n];
for (int i = 0; i < n; i++) {
nextGraph[i] = new ArrayList<int[]>();
preGraph[i] = new ArrayList<int[]>();
}

for (int[] edge : edges) {
int from = edge, to = edge, weight = edge;
nextGraph[from].add(new int[] {to, weight});
preGraph[to].add(new int[] {from, weight});
}
}

private void shortestPath(int src, long[] srcTo, ArrayList<int[]>[] graph) {
PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a, b));
heap.offer(new long[] {src, 0});

while (!heap.isEmpty()) {
long[] node = heap.poll();
int to = (int) node;
long dist = node;
if (srcTo[to] != -1 && srcTo[to] <= dist) continue;
srcTo[to] = dist;
for (int[] next : graph[to]) {
heap.offer(new long[] {next, dist + next});
}
}
}
}
``````

### Minimum Weighted Subgraph With the Required Paths Leetcode Solution in Python 3

``````class Solution:
def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
graph, reverse_graph = defaultdict(list), defaultdict(list)
for i, j, w in edges:
graph[i].append((j, w))
reverse_graph[j].append((i, w))

def dijkstra(src, G):
distance = [-1] * n
pq = [(0, src)]
while pq:
w, node = heappop(pq)
if distance[node] >= 0:
continue
distance[node] = w
for nxt, wt in G[node]:
if distance[nxt] < 0:
heappush(pq, (w + wt, nxt))
return distance

l1 = dijkstra(src1, graph)
l2 = dijkstra(src2, graph)
l3 = dijkstra(dest, reverse_graph)
best_dist = -1
for i in range(n):
if l1[i] >= 0 and l2[i] >= 0 and l3[i] >= 0:
cur_dist = l1[i] + l2[i] + l3[i]
if best_dist < 0 or cur_dist < best_dist:
best_dist = cur_dist
return best_dist
``````
##### Weekly Contest 284 LeetCode Solution Review:

In our experience, we suggest you solve this Weekly Contest 284 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 Weekly Contest 284 LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Weekly Contest 284 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