703795. Query and Array
Easy
Query and Array
Slug: query-and-array4947
Difficulty: Easy
Id: 703795
Topic Tags: Arrays, Bit Magic, Data Structures
Company Tags: None
Summary
Given an array arr of size n, write a function to find the number of queries that can be made without violating any constraints. A query is considered valid if the difference between the maximum and minimum values in the subarray from index i to j (both inclusive) does not exceed k. The function should return the total number of valid queries.
Detailed Explanation
To solve this problem, we can use a simple brute-force approach. We iterate over all possible query ranges [i, j] and check if the difference between the maximum and minimum values in the subarray does not exceed k.
Here's a step-by-step breakdown:
- Initialize a variable
queriesto store the total number of valid queries. - Iterate over all possible query ranges
[i, j]. - For each query range, calculate the maximum and minimum values in the subarray using two pointers
maxandmin, initialized at indicesiandjrespectively. - Update the maximum value if the current element is greater than
max, or update the minimum value if the current element is smaller thanmin. - Check if the difference between
maxandmindoes not exceedk. If it does, increment thequeriesvariable. - Return the total number of valid queries.
Time complexity: O(n^2) due to the nested loops. Space complexity: O(1) as we only use a few extra variables.
Optimized Solutions
Java
public int queryAndArray(int[] arr, int k) {
int n = arr.length;
int queries = 0;
for (int i = 0; i < n; i++) {
int max = arr[i];
int min = arr[i];
for (int j = i; j < n; j++) {
max = Math.max(arr[j], max);
min = Math.min(arr[j], min);
if (max - min <= k) {
queries++;
}
}
}
return queries;
}