DDSA Solutions

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

MediumView on LeetCode
Array
Time: O(n)
Space: O(1)

Problem Overview

Check if at most one swap can make all 1s move to the right end.

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

  1. 1Find last index of 1.
  2. 2Count 0s in range [0, last_one_index].
  3. 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
C#
// 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?

Related Problems