Welcome to Subscribe On Youtube

3532. Path Existence Queries in a Graph I

Description

You are given an integer n representing the number of nodes in a graph, labeled from 0 to n - 1.

You are also given an integer array nums of length n sorted in non-decreasing order, and an integer maxDiff.

An undirected edge exists between nodes i and j if the absolute difference between nums[i] and nums[j] is at most maxDiff (i.e., \|nums[i] - nums[j]\| <= maxDiff).

You are also given a 2D integer array queries. For each queries[i] = [ui, vi], determine whether there exists a path between nodes ui and vi.

Return a boolean array answer, where answer[i] is true if there exists a path between ui and vi in the ith query and false otherwise.

 

Example 1:

Input: n = 2, nums = [1,3], maxDiff = 1, queries = [[0,0],[0,1]]

Output: [true,false]

Explanation:

  • Query [0,0]: Node 0 has a trivial path to itself.
  • Query [0,1]: There is no edge between Node 0 and Node 1 because \|nums[0] - nums[1]\| = \|1 - 3\| = 2, which is greater than maxDiff.
  • Thus, the final answer after processing all the queries is [true, false].

Example 2:

Input: n = 4, nums = [2,5,6,8], maxDiff = 2, queries = [[0,1],[0,2],[1,3],[2,3]]

Output: [false,false,true,true]

Explanation:

The resulting graph is:

  • Query [0,1]: There is no edge between Node 0 and Node 1 because \|nums[0] - nums[1]\| = \|2 - 5\| = 3, which is greater than maxDiff.
  • Query [0,2]: There is no edge between Node 0 and Node 2 because \|nums[0] - nums[2]\| = \|2 - 6\| = 4, which is greater than maxDiff.
  • Query [1,3]: There is a path between Node 1 and Node 3 through Node 2 since \|nums[1] - nums[2]\| = \|5 - 6\| = 1 and \|nums[2] - nums[3]\| = \|6 - 8\| = 2, both of which are within maxDiff.
  • Query [2,3]: There is an edge between Node 2 and Node 3 because \|nums[2] - nums[3]\| = \|6 - 8\| = 2, which is equal to maxDiff.
  • Thus, the final answer after processing all the queries is [false, false, true, true].

 

Constraints:

  • 1 <= n == nums.length <= 105
  • 0 <= nums[i] <= 105
  • nums is sorted in non-decreasing order.
  • 0 <= maxDiff <= 105
  • 1 <= queries.length <= 105
  • queries[i] == [ui, vi]
  • 0 <= ui, vi < n

Solutions

Solution 1: Grouping

According to the problem description, the node indices within the same connected component must be consecutive. Therefore, we can use an array $g$ to record the connected component index for each node and a variable $\textit{cnt}$ to track the current connected component index. As we iterate through the $\textit{nums}$ array, if the difference between the current node and the previous node is greater than $\textit{maxDiff}$, it indicates that the current node and the previous node are not in the same connected component. In this case, we increment $\textit{cnt}$. Then, we assign the current node’s connected component index to $\textit{cnt}$.

Finally, for each query $(u, v)$, we only need to check whether $g[u]$ and $g[v]$ are equal. If they are equal, it means $u$ and $v$ are in the same connected component, and the answer for the $i$-th query is $\text{true}$. Otherwise, the answer is $\text{false}$.

The complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the $\textit{nums}$ array.

  • class Solution { public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) { int[] g = new int[n]; int cnt = 0; for (int i = 1; i < n; ++i) { if (nums[i] - nums[i - 1] > maxDiff) { cnt++; } g[i] = cnt; } int m = queries.length; boolean[] ans = new boolean[m]; for (int i = 0; i < m; ++i) { int u = queries[i][0]; int v = queries[i][1]; ans[i] = g[u] == g[v]; } return ans; } } 
  • class Solution { public: vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) { vector<int> g(n); int cnt = 0; for (int i = 1; i < n; ++i) { if (nums[i] - nums[i - 1] > maxDiff) { ++cnt; } g[i] = cnt; } vector<bool> ans; for (const auto& q : queries) { int u = q[0], v = q[1]; ans.push_back(g[u] == g[v]); } return ans; } }; 
  • class Solution: def pathExistenceQueries( self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]] ) -> List[bool]: g = [0] * n cnt = 0 for i in range(1, n): if nums[i] - nums[i - 1] > maxDiff: cnt += 1 g[i] = cnt return [g[u] == g[v] for u, v in queries] 
  • func pathExistenceQueries(n int, nums []int, maxDiff int, queries [][]int) (ans []bool) { g := make([]int, n) cnt := 0 for i := 1; i < n; i++ { if nums[i]-nums[i-1] > maxDiff { cnt++ } g[i] = cnt } for _, q := range queries { u, v := q[0], q[1] ans = append(ans, g[u] == g[v]) } return } 
  • function pathExistenceQueries( n: number, nums: number[], maxDiff: number, queries: number[][], ): boolean[] { const g: number[] = Array(n).fill(0); let cnt = 0; for (let i = 1; i < n; ++i) { if (nums[i] - nums[i - 1] > maxDiff) { ++cnt; } g[i] = cnt; } return queries.map(([u, v]) => g[u] === g[v]); }

All Problems

All Solutions