How to Solve ‘containsCloseNums’ in CodeFights

The Problem:

Given an array of integers nums and an integer k, determine whether there are two distinct indices i and j in the array wherenums[i] = nums[j] and the absolute difference between i and j is less than or equal to k.

Example

  • For nums = [0, 1, 2, 3, 5, 2] and k = 3, the output should be
    containsCloseNums(nums, k) = true.

    There are two 2s in nums, and the absolute difference between their positions is exactly 3.

  • For nums = [0, 1, 2, 3, 5, 2] and k = 2, the output should be

    containsCloseNums(nums, k) = false.

    The absolute difference between the positions of the two 2s is 3, which is more than k.

Input/Output

  • [time limit] 4000ms (py)
  • [input] array.integer nums

    Constraints:
    0 ≤ nums.length ≤ 55000,
    -231 - 1 ≤ nums[i] ≤ 231 - 1.

  • [input] integer k

    Constraints:
    0 ≤ k ≤ 35000.

  • [output] boolean

The Solution:

asddasdasdas16

The Explanation:

First of all, we can solve this by running two loops, one is i from 1 to k and the other j from 0 to len(nums)-i and compare nums[j] and nums[i+j]. If we find an equality, return 1. If none found, return 0.

However, we would receive Time Limit Exceeded Error. So, we need a better solution. We know that when we sort numbers, the same numbers will be consecutive in sorted order. So, if we store the original locations of all elements, we will have the same elements together and also know their original location. All we have to do now is to check if any consecutive equal numbers have a smaller distance than k+1.

This reduces our complexity from, let’s say len(nums) = n. Then, O(n*k) to O( n*log(n) )

limit of n is 55000 so, logn is approximately 16. Where k could be 35000. So, our worst case scenario becomes 55000*35000 to 55000*16.

How we do this is simple. First,generate a new array with numbers and their original addressses. Then, sort them using their values. Then, for each element, check if the previous element has the same value, if so, check their original location distances. If smaller than k+1, return 1

Otherwise, return 0

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s