Solution by sanya2371


  • 0
    S

    Approach #1 Brute Force [Time Limit Exceeded]

    Intuition

    The simplest and the most intuitive solution is iterate through all elements and compare them with all other elements.

    Algorithm

    • Start first cycle at i=0 element of the array and iterate to the nums.Lenght - 1 element.
    • Start second cycle at j = i + 1 element (so that we do not compare all previous elements, that were already compared) and go to the end of the array.
    • Compare each nums[i] element with nums[j] element and if they are equal add nums[i] element to the result collection.

    C#

    public class Solution {
       public IList<int> FindDuplicates(int[] nums)  {
            var result = new List<int>();
            for (int i = 0; i < nums.Length - 1; i++) {
                for (int j = i + 1; j < nums.Length; j++) {
                    if (nums[i] == nums[j])
                        result.Add(nums[i]);
                }
            }
            return result;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n^2)$$.
    • Space complexity : $$O(1)$$.

    Approach #2 Using HashSet [Accepted]

    Intuition

    To optimize time complexity we can use HashSet as it allows us to check quickly if we already have seen specific element. HashSet time complexity of Add and Contains operations is $$O(1)$$.

    Algorithm

    • Iterate through all elements in the array.
    • Check if hashSet contains current element, if true add it to result collection, otherwise add current element to hashSet.

    C#

    public class Solution {
        public IList<int> FindDuplicates(int[] nums) {
            var result = new List<int>();
            var hashSet = new HashSet<int>();
            foreach (int n in nums) {
                if (hashSet.Contains(n)) {
                    result.Add(n);
                } else {
                    hashSet.Add(n);
                }
            }
            return result;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.
    • Space complexity : $$O(n)$$.

    Approach #3 Modifing sourcr array [Accepted]

    Intuition

    If we are allowed to modify source array, we can further improve both time and space complexity. As we know from description 1 ≤ a[i] ≤ n, so we can use array elements as indexes to mark visited elements.

    Algorithm

    • Iterate through all elements in the array.
    • Use absolute element value minus 1 as index.
    • If element at index is greater than 0, change its sign to - (so we can check in further iterations if we saw this element), else add index + 1 to result collection.

    C#

    public class Solution {
        public IList<int> FindDuplicates(int[] nums) {
            var result = new List<int>();
            foreach (int n in nums) {
                int index = Math.Abs(n) - 1;
                if (nums[index] > 0) {
                    nums[index] = -nums[index];
                } else {
                    result.Add(index + 1);
                }
            }
            return result;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.
    • Space complexity : $$O(1)$$.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.