Find All K-Distant Indices in an Array

🏠 ⬅️ ➡️

You are given a 0-indexed integer array nums and two integers key and k. A k-distant index is an index i of nums for which there exists at least one index j such that |i - j| <= k and nums[j] == key.

Return a list of all k-distant indices sorted in increasing order.

Example 1:

Input: nums = [3,4,9,1,3,9,5], key = 9, k = 1 Output: [1,2,3,4,5,6] Explanation: Here, nums[2] == key and nums[5] == key. - For index 0, |0 - 2| > k and |0 - 5| > k, so there is no j where |0 - j| <= k and nums[j] == key. Thus, 0 is not a k-distant index. - For index 1, |1 - 2| <= k and nums[2] == key, so 1 is a k-distant index. - For index 2, |2 - 2| <= k and nums[2] == key, so 2 is a k-distant index. - For index 3, |3 - 2| <= k and nums[2] == key, so 3 is a k-distant index. - For index 4, |4 - 5| <= k and nums[5] == key, so 4 is a k-distant index. - For index 5, |5 - 5| <= k and nums[5] == key, so 5 is a k-distant index. - For index 6, |6 - 5| <= k and nums[5] == key, so 6 is a k-distant index. Thus, we return [1,2,3,4,5,6] which is sorted in increasing order.

Example 2:

Input: nums = [2,2,2,2,2], key = 2, k = 2 Output: [0,1,2,3,4] Explanation: For all indices i in nums, there exists some index j such that |i - j| <= k and nums[j] == key, so every index is a k-distant index. Hence, we return [0,1,2,3,4].

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • key is an integer from the array nums.
  • 1 <= k <= nums.length
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 7
    integer, parameter :: k = 1
    integer, parameter :: key = 9
    integer :: nums(n) = [3, 4, 9, 1, 3, 9, 5]
    integer :: i, j
    logical :: found

    do i = 1, n
        found = .false.
        do j = max(1, i - k), min(n, i + k)
            if (abs(i - j) <= k .and. nums(j) == key) then
                found = .true.
                exit
            end if
        end do
        if (found) then
            write (*, '(I0)') i
        end if
    end do

end program main
❌ Compiled
❌ Executed
❌ Correct 
module k_distant_indices
    implicit none

contains

    function k_distant_indices(nums, key, k) result(indices)
        integer, intent(in) :: nums(:), key, k
        integer :: indices(size(nums))

        ! Initialize the indices array with the indices of the key elements
        indices = pack(reshape((/(i, i = 1, size(nums))/), shape(nums)), &
                       nums == key)

        ! Sort the indices in increasing order
        indices = sort(indices)

        ! Remove the indices that are not k-distant
        indices = indices(k_distant_mask(nums, key, k))

        ! Return the sorted indices
        return
    end function k_distant_indices

    function k_distant_mask(nums, key, k) result(mask)
        integer, intent(in) :: nums(:), key, k
        logical :: mask(size(nums))

        ! Initialize the mask with the indices of the key elements
        mask = nums == key

        ! Remove the indices that are not k-distant
        mask = mask .and. k_distant(nums, key, k)

        ! Return the mask
        return
    end function k_distant_mask

    function k_distant(nums, key, k) result(distant)
        integer, intent(in) :: nums(:), key, k
        logical :: distant(size(nums))

        ! Initialize the distant array with the indices of the key elements
        distant = pack(reshape((/(i, i = 1, size(nums))/), shape(nums)), &
                       nums == key)

        ! Remove the indices that are not k-distant
        distant = distant .and. k_distant_helper(nums, key, k)

        ! Return the distant array
        return
    end function k_distant

    function k_distant_helper(nums, key, k) result(distant)
        integer, intent(in) :: nums(:), key, k
        logical :: distant(size(nums))

        ! Initialize the distant array with the indices of the key elements
        distant = pack(reshape((/(i, i = 1, size(nums))/), shape(nums)), &
                       nums == key)

        ! Remove the indices that are not k-distant
        do i = 1, size(nums)
            distant(i) = distant(i) .and. any(abs(i - distant) <= k)
        end do

        ! Return the distant array
        return
    end function k_distant_helper
end module k_distant_indices

program test_k_distant_indices
    use k_distant_indices
    implicit none

    integer, parameter :: nums(7) = [3, 4, 9, 1, 3, 9, 5]
    integer, parameter :: key = 9
    integer, parameter :: k = 1
    integer :: indices(size(nums))

    indices = k_distant_indices(nums, key, k)

    write (*,*) indices

end program test_k_distant_indices
🌐 Data from online sources 
def can_fit_stamps(grid, stampHeight, stampWidth):
    m, n = len(grid), len(grid[0])
    for i in range(m - stampHeight + 1):
        for j in range(n - stampWidth + 1):
            canFit = True
            for x in range(stampHeight):
                for y in range(stampWidth):
                    if grid[i + x][j + y] == 1:
                        canFit = False
                        break
                if not canFit:
                    break
            if canFit:
                return True
    return False

The algorithm loops through the cells of the grid, and for each cell, it checks if a stamp can fit the area starting from that cell. If the stamp fits without any occupied cells (value of 1) in the area, the function returns true. If the loop finishes without finding any fitting area, the function returns false.

🌐 Data from online sources 
bool canFitStamps(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
    int m = grid.size(), n = grid[0].size();
    for (int i = 0; i + stampHeight - 1 < m; ++i) {
        for (int j = 0; j + stampWidth - 1 < n; ++j) {
            bool canFit = true;
            for (int x = 0; x < stampHeight && canFit; ++x) {
                for (int y = 0; y < stampWidth && canFit; ++y) {
                    if (grid[i + x][j + y] == 1) {
                        canFit = false;
                    }
                }
            }
            if (canFit) {
                return true;
            }
        }
    }
    return false;
}

The algorithm loops through the cells of the grid, and for each cell, it checks if a stamp can fit the area starting from that cell. If the stamp fits without any occupied cells (value of 1) in the area, the function returns true. If the loop finishes without finding any fitting area, the function returns false.