Home/ Questions/Q 263
In Process
Anonymous
  • 0
Asked: 2022-12-29T17:31:15+00:00 In:

How to Solve this coding interview problem in linear time complexity

  • 0

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

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

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

array

You must login to add an answer.

Need An Account,

1 Answer

  1. Begginer

    To solve this problem in linear time complexity (O(n)), you can use the following algorithm:

    1. Initialize an empty set called duplicates.
    2. Iterate through the array, and for each element x in the array: a. If x is in duplicates, return true. b. Otherwise, add x to duplicates.
    3. If the loop completes, return false.

    Here is some example code in Python that implements this algorithm:

    def containsDuplicate(nums):
    duplicates = set()
    for x in nums:
      if x in duplicates:
      return True
    duplicates.add(x)
    return False

    This algorithm has a time complexity of O(n), as it requires iterating through the array once and performing a constant number of operations for each element.

    I hope this helps! Let me know if you have any questions.

    • 0