Sponsored
Sponsored
This approach involves iterating through the array and keeping track of the most recent index where a '1' has been encountered. For every '1' encountered, check if the distance from the last '1' is at least 'k'. If any distance is found to be less than 'k', return false. If the loop ends without returning false, return true.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), as only a few variables are used.
1#include <stdbool.h>
2
3bool kLengthApart(int* nums, int numsSize, int k) {
4 int lastIndex = -1; // mark the last position of 1
5 for (int i = 0; i < numsSize; i++) {
6 if (nums[i] == 1) {
7 if (lastIndex != -1 && i - lastIndex - 1 < k) {
8 return false;
9 }
10 lastIndex = i;
11 }
12 }
13 return true;
14}The code defines a function that iterates over the entire array, keeping track of the last index where '1' occurred. If another '1' is found and the distance from the last occurrence is less than k, it returns false. Otherwise, it updates the last index and continues scanning.
This method includes scanning the array to compute gaps between '1's using a counter. If the gap calculated is ever less than k while traversing, return false. This process continues until the scan ends, signifying all gaps are adequate, thus returning true.
Time Complexity: O(n), with n being the size of nums array.
Space Complexity: O(1), utilizing constant space to track count.
using namespace std;
class Solution {
public:
bool areGapsValid(vector<int>& nums, int k) {
int count = k;
for (int num : nums) {
if (num == 1) {
if (count < k) return false;
count = 0;
} else {
count++;
}
}
return true;
}
};In this C++ code, the function iterates through the vector, using a count to track spaces between 1s. If it finds that a '1' is too close to the previous one, it returns false.