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

🏠 ⬅️ ➡️

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 <= 105
  • 0 <= k <= nums.length
  • nums[i] is 0 or 1
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    ! Solve the problem:
    ! 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`.
    implicit none

    integer, parameter :: k = 2
    integer, dimension(8) :: nums = [1, 0, 0, 0, 1, 0, 0, 1]
    logical :: result

    print '(L1)', solve(nums, k)

contains

    function solve(nums, k) result(result)
        implicit none
        integer, dimension(:), intent(in) :: nums
        integer, intent(in) :: k
        logical :: result
        integer :: i, j, n

        n = size(nums)
        do i = 1, n - k
            do j = i + 1, min(n, i + k)
                if (nums(i) == 1 .and. nums(j) == 1) then
                    result = .false.
                    return
                end if
            end do
        end do
        result = .true.
    end function solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
```
program is_k_distance_apart
    implicit none
    integer, parameter :: k = 2
    integer, dimension(8) :: nums = [1, 0, 0, 0, 1, 0, 0, 1]
    logical :: result

    result = is_k_distance_apart(nums, k)

    if (result) then
        print *, "All 1s are at least ", k, " places away from each other."
    else
        print *, "Not all 1s are at least ", k, " places away from each other."
    end if

contains

    function is_k_distance_apart(nums, k) result(is_apart)
        implicit none
        integer, dimension(:), intent(in) :: nums
        integer, intent(in) :: k
        logical :: is_apart
        integer :: i, j

        is_apart = .true.

        do i = 1, size(nums) - k
            if (nums(i) == 1) then
                do j = i + 1, i + k
                    if (nums(j) == 1) then
                        is_apart = .false.
                        exit
                    end if
                end do
                if (.not. is_apart) exit
            end if
        end do
    end function is_k_distance_apart
end program is_k_distance_apart
```
🌐 Data from online sources 
def min_steps_to_make_palindrome(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

We use dynamic programming to find the minimum number of steps required to make a string palindrome. The dp[i][j] element of the 2D dp array represents the minimum number of steps required to make a palindrome from substring s[i..j]. We iterate through the string in reverse order, and for each pair of characters, if the characters are equal, we update the dp[i][j] value using the dp[i+1][j-1]. If they are not equal, we update the dp[i][j] using the minimum value between dp[i+1][j] and dp[i][j-1], adding 1 to it. In the end, we return the value at dp[0][n-1], which represents the minimum steps required to make the whole string palindrome.

🌐 Data from online sources 
int minStepsToMakePalindrome(std::string s) {
    int n = s.size();
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));

    for (int i = n - 2; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1];
            } else {
                dp[i][j] = 1 + std::min(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[0][n - 1];
}

We use dynamic programming to find the minimum number of steps required to make a string palindrome. The dp[i][j] element of the 2D dp array represents the minimum number of steps required to make a palindrome from substring s[i..j]. We iterate through the string in reverse order, and for each pair of characters, if the characters are equal, we update the dp[i][j] value using the dp[i+1][j-1]. If they are not equal, we update the dp[i][j] using the minimum value between dp[i+1][j] and dp[i][j-1], adding 1 to it. In the end, we return the value at dp[0][n-1], which represents the minimum steps required to make the whole string palindrome.