Given an binary array nums and an integer k, return true if all 1's are at least k places away from each other, otherwise return false.
Example 1:
Input: nums = [1,0,0,0,1,0,0,1], k = 2 Output: true Explanation: Each of the 1s are at least 2 places away from each other.
Example 2:
Input: nums = [1,0,0,1,0,1], k = 2 Output: false Explanation: The second 1 and third 1 are only one apart from each other.
Constraints:
1 <= nums.length <= 1050 <= k <= nums.lengthnums[i] is 0 or 1This 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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), as only a few variables are used.
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.
The solution checks each element, increasing count when a '0' is found and resetting or checking it when a '1' appears. If count is ever less than k upon seeing '1', false is returned instantly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), with n being the size of nums array.
Space Complexity: O(1), utilizing constant space to track count.
| Approach | Complexity |
|---|---|
| Simple Linear Scan | Time Complexity: O(n), where n is the number of elements in nums. Space Complexity: O(1), as only a few variables are used. |
| Calculating Gaps Between 1s | Time Complexity: O(n), with n being the size of nums array. Space Complexity: O(1), utilizing constant space to track count. |
Check If All 1's Are at Least Length K Places Away|| Leetcode || C++ • Code with Alisha • 771 views views
Watch 9 more video solutions →Practice Check If All 1's Are at Least Length K Places Away with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor