Contains Duplicate II

🏠 ⬅️ ➡️

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3 Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1 Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2 Output: false

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 4
    integer, dimension(n) :: nums
    integer :: k
    logical :: result

    ! Example 1
    nums = [1, 2, 3, 1]
    k = 3
    result = contains_duplicate(nums, k)
    print '(L1)', result

    ! Example 2
    nums = [1, 0, 1, 1]
    k = 1
    result = contains_duplicate(nums, k)
    print '(L1)', result

    ! Example 3
    nums = [1, 2, 3, 1, 2, 3]
    k = 2
    result = contains_duplicate(nums, k)
    print '(L1)', result

contains

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

        res = .false.
        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (nums(i) == nums(j)) then
                    if (abs(i - j) <= k) then
                        res = .true.
                        exit
                    end if
                end if
            end do
        end do
    end function contains_duplicate
end program main
❌ Compiled
❌ Executed
❌ Correct 
module has_duplicate_value_within_k
    implicit none
    private
    public :: has_duplicate_value_within_k

contains

    logical function has_duplicate_value_within_k(nums, k) result(has_duplicate)
        integer, intent(in) :: nums(:)
        integer, intent(in) :: k
        integer :: i, j

        has_duplicate = .false.

        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (nums(i) == nums(j) .and. abs(i - j) <= k) then
                    has_duplicate = .true.
                    exit
                end if
            end do
            if (has_duplicate) exit
        end do
    end function has_duplicate_value_within_k
end module has_duplicate_value_within_k

program test_has_duplicate_value_within_k
    use has_duplicate_value_within_k
    implicit none
    integer, parameter :: nums1(4) = [1, 2, 3, 1]
    integer, parameter :: nums2(5) = [1, 0, 1, 1, 2]
    integer, parameter :: nums3(6) = [1, 2, 3, 1, 2, 3]
    integer, parameter :: k1 = 3
    integer, parameter :: k2 = 1
    integer, parameter :: k3 = 2

    write (*, '(A)') 'Test 1:'
    if (has_duplicate_value_within_k(nums1, k1)) then
        write (*, '(A)') 'Passed!'
    else
        write (*, '(A)') 'Failed!'
    end if

    write (*, '(A)') 'Test 2:'
    if (has_duplicate_value_within_k(nums2, k2)) then
        write (*, '(A)') 'Passed!'
    else
        write (*, '(A)') 'Failed!'
    end if

    write (*, '(A)') 'Test 3:'
    if (.not. has_duplicate_value_within_k(nums3, k3)) then
        write (*, '(A)') 'Passed!'
    else
        write (*, '(A)') 'Failed!'
    end if
end program test_has_duplicate_value_within_k
🌐 Data from online sources 
def containsNearbyDuplicate(nums, k):
    value_index_map = {}
    for i, num in enumerate(nums):
        if num in value_index_map and i - value_index_map[num] <= k:
            return True
        value_index_map[num] = i
    return False

The algorithm utilizes a Hashtable, in which we store the integer value present in the array as the key and its latest index position as the value. For each element in the array, we first check if the current number is already in the Hashtable. If it is, we also check if the difference between the current index and the latest index stored in the Hashtable is less than or equal to k. If both conditions are met, we return true because there are two repeating integers having an index difference less than or equal to k. Otherwise, we add the number along with its latest index to the Hashtable and continue with the next element. If the loop finishes without finding such a pair, we return false.

Note: The algorithm's time complexity is O(n), where n is the length of the input array, and the space complexity is O(min(n, k)).

🌐 Data from online sources 
bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int, int> valueIndexMap;
    for (int i = 0; i < nums.size(); i++) {
        if (valueIndexMap.find(nums[i]) != valueIndexMap.end() && i - valueIndexMap[nums[i]] <= k) {
            return true;
        }
        valueIndexMap[nums[i]] = i;
    }
    return false;
}

The algorithm utilizes a Hashtable, in which we store the integer value present in the array as the key and its latest index position as the value. For each element in the array, we first check if the current number is already in the Hashtable. If it is, we also check if the difference between the current index and the latest index stored in the Hashtable is less than or equal to k. If both conditions are met, we return true because there are two repeating integers having an index difference less than or equal to k. Otherwise, we add the number along with its latest index to the Hashtable and continue with the next element. If the loop finishes without finding such a pair, we return false.

Note: The algorithm's time complexity is O(n), where n is the length of the input array, and the space complexity is O(min(n, k)).