Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

Arrays Intersection

Array, Hash Table

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000

  • 0 <= nums1[i], nums2[i] <= 1000

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?

  • What if num1's size is small compared to nums2's size? Which algorithm is better?

  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solutions

Approach - Brute Force Technique

It works by checking each element of the first array against the second array and adding it to the intersection if it exists. The second array is represented as a list so that elements can be easily removed. This ensures that each element is counted the correct number of times.

Steps

  1. Initialize intersection and list2: A new List intersection is created to store the intersection of nums1 and nums2. Another List list2 is created as a copy of nums2. This is done because elements will be removed from list2 during the process, and we don’t want to modify the original array.

  2. Iterate over nums1: The method iterates over each element num in nums1.

  3. Check if num exists in list2: For each num in nums1, the method checks if num exists in list2 using the Contains method.

  4. Add num to intersection and remove from list2: If num exists in list2, it is added to intersection and removed from list2. The Remove method removes the first occurrence of num from list2. This ensures that each element in the intersection appears as many times as it shows in both arrays.

  5. Return intersection as an array: After all elements in nums1 have been processed, the ToArray method is called on intersection to convert it back to an array before returning it as the result of the method.

public class Solution
{
    public int[] Intersect(int[] nums1, int[] nums2)
    {
        List<int> intersection = new List<int>();
        List<int> list2 = new List<int>(nums2);

        foreach (int num in nums1)
        {
            if (list2.Contains(num))
            {
                intersection.Add(num);
                list2.Remove(num);
            }
        }

        return intersection.ToArray();
    }
}

Approach - Hash Table Technique

Steps

  1. Initialization: The function Intersect is defined with two parameters, nums1 and nums2, which are the input arrays. It initializes a dictionary dict to keep track of the frequency of each number in nums1, and a list res to store the result.

  2. Create Frequency Dictionary: The function iterates over each number in nums1. For each number, it checks if the number is already a key in dict. If it is, it increments the value associated with that key. If not, it adds the number as a key to dict with a value of 1. This results in dict containing each unique number in nums1 as a key, and the frequency of that number as the value.

  3. Find Intersection: The function then iterates over each number in nums2. For each number, it checks if the number is a key in dict and if the associated value is greater than 0. If both conditions are met, it means the number is present in both nums1 and nums2, so it adds the number to res and decrements the value associated with the number in dict.

  4. Return Result: Finally, the function converts res to an array and returns it. This array contains the intersection of nums1 and nums2.

public class Solution {
    public int[] Intersect(int[] nums1, int[] nums2) {
        
        var dict = new Dictionary<int, int>();
        var res = new List<int>();

        foreach (var num in nums1)
        {
            if (dict.ContainsKey(num))
                dict[num]++;
            else
                dict[num] = 1;
        }

         foreach (var num in nums2)
        {
            if (dict.ContainsKey(num) && dict[num]>0)
            {
                res.Add(num);
                dict[num]--;
            }
        }

        return res.ToArray();
    }
}

Complexity

  • Time complexity: O(N+M)

  • Space complexity: O(N)

PreviousMerge Sorted ArraysNext3Sum

Last updated 1 year ago