1437. Check If All 1's Are at Least Length K Places Away

MediumView on LeetCode

Array

Time: O(n)

Space: O(1)

Intuition

Check if at most one swap can make all 1s move to the right end. Count 0s before the last 1 - if <= 1, possible.

Algorithm

1Find last index of 1.
2Count 0s in range [0, last_one_index].
3Return count <= 1.

Common Pitfalls

•At most one 0 can appear before the last 1 (one swap can fix one 0 by swapping with the last 1).

1437.cs

// Approach: Track the index of the previous '1'; return false if any gap between consecutive 1s is less than k.
// Time: O(n) Space: O(1)

public class Solution
{
    public bool KLengthApart(int[] nums, int k)
    {
        // Initialize the position of the previous 1
        // Set to -(k+1) to handle the case when the first element is 1
        // This ensures the distance check passes for the first 1
        int previousOneIndex = -(k + 1);

        // Iterate through the array to find all 1s
        for (int currentIndex = 0; currentIndex < nums.Length; currentIndex++)
        {
            // Check if current element is 1
            if (nums[currentIndex] == 1)
            {
                // Calculate distance between current 1 and previous 1
                // Distance = currentIndex - previousOneIndex - 1 (excluding both endpoints)
                if (currentIndex - previousOneIndex - 1 < k)
                    // Distance is less than k, so return false
                    return false;

                // Update the position of the previous 1
                previousOneIndex = currentIndex;
            }
        }

        // All 1s are at least k distance apart
        return true;
    }
}

Was this solution helpful?