Intersection of two sorted arrays

Intuition

Imagine you are organizing two different guest lists for two separate events. Some guests are invited to both events, and you want to create a new list of guests who are attending both.

Here’s how you can figure it out:

Start by going through the first guest list. For each guest in the first list, check if they are also on the second guest list. If you find a guest who is on both lists, add them to your new list of common guests, but make sure not to add the same guest more than once.

Approach

Create an array called visited of the same size as nums2 to keep track of elements that have already been checked in nums2.

Iterate through loop (let's call the loop variable i) to go through each element in nums1.

For each element in nums1, use another for loop (let's call the loop variable j) to iterate through nums2.

For each element nums1[i], check if it is equal to nums2[j] and also ensure visited[j] is 0 (meaning this element of nums2 has not been visited yet).

If both conditions are met, add nums1[i] to the result array ans and mark visited[j] as 1 to indicate that nums2[j] has been processed.

Repeat the above steps until all elements in nums1 have been compared with all elements in nums2.

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    //Function to find intersection of two sorted arrays
    vector<int> intersectionArray(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        // To maintain visited status
        vector<int> visited(nums2.size(), 0);
   
        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {

               /*If nums1[i] is equal to nums2[j] and nums2[j]
               is not visited then add nums2[j] in ans.*/
                if (nums1[i] == nums2[j] && visited[j] == 0) {
                    ans.push_back(nums2[j]);
                    
                    // Mark as visited
                    visited[j] = 1;
                    
                    break;
                } 
                /** If num2[j] is greater than nums1[i] 
                break out of the loop */
                else if (nums2[j] > nums1[i])
                    break; 
            }
        }
       //Return ans vector
        return ans;
    }
};

int main() {
    vector<int> nums1 = {1, 2, 3, 3, 4, 5, 6, 7};
    vector<int> nums2 = {3, 3, 4, 4, 5, 8};

    // Create an instance of the Solution class
    Solution finder;

    // Get intersection of nums1 and nums2 using class method
    vector<int> ans = finder.intersectionArrays(nums1, nums2);

    cout << "Intersection of nums1 and nums2 is:" << endl;
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}
import java.util.*;

class Solution {
    //Function to find intersection of two sorted arrays
    public int[] intersectionArray(int[] nums1, int[] nums2) {
        List<Integer> ansList = new ArrayList<>();
        int[] visited = new int[nums2.length];

        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {

                /*If nums1[i] is equal to nums2[j] and nums2[j] 
                is not visited then add nums2[j] in ans.*/
                if (nums1[i] == nums2[j] && visited[j] == 0) {
                    
                    ansList.add(nums2[j]);
                    // Mark as visited
                    visited[j] = 1;
                    
                    break;
                } 
                 //If nums2[j] is greater than nums1[i], break out of loop
                else if (nums2[j] > nums1[i]) 
                    break; 
            }
        }

        // Convert ArrayList to int array
        int[] ans = new int[ansList.size()];
        for (int k = 0; k < ansList.size(); k++) {
            ans[k] = ansList.get(k);
        }
       
       //Return the final ans
        return ans;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 3, 4, 5, 6, 7};
        int[] nums2 = {3, 3, 4, 4, 5, 8};

        // Create an instance of the Solution class
        Solution finder = new Solution();

        int[] ans = finder.intersectionArrays(nums1, nums2);

        //Print the intersection of both arrays
        System.out.println("Intersection of nums1 and nums2 is:");
        for (int val : ans) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}
from typing import List

class Solution:
    #Function to find intersection of two sorted arrays
    def intersectionArray(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans_list = []
        visited = [0] * len(nums2)
        i, j = 0, 0

        while i < len(nums1):
            while j < len(nums2):

                """ If nums1[i] is equal to nums2[j] and nums2[j] is
                    not visited then add nums2[j] in ans. """
                if nums1[i] == nums2[j] and visited[j] == 0:
                    
                    ans_list.append(nums2[j])
                    # Mark as visited
                    visited[j] = 1
                    
                    break
                 #If nums2[j] is greater than nums1[i], break out of loop
                elif nums2[j] > nums1[i]:
                    break
                j += 1
            i += 1
       
       #Return the final ans
        return ans_list

    def main(self):
        nums1 = [1, 2, 3, 3, 4, 5, 6, 7]
        nums2 = [3, 3, 4, 4, 5, 8]

        # Create an instance of the Solution class
        finder = Solution()

        # Get intersection of nums1 and nums2 using class method
        ans = finder.intersectionArrays(nums1, nums2)

        print("Intersection of nums1 and nums2 is:")
        print(ans)

if __name__ == "__main__":
    Solution().main()
class Solution {
    //Function to find intersection of two sorted arrays
    intersectionArray(nums1, nums2) {
        let ansList = [];
        let visited = new Array(nums2.length).fill(0);
        let i = 0, j = 0;

        while (i < nums1.length) {
            while (j < nums2.length) {

               /*If nums1[i] is equal to nums2[j] and nums2[j]
                is not visited then add nums2[j] in ans.*/
                if (nums1[i] === nums2[j] && visited[j] === 0) {
                    ansList.push(nums2[j]);
                    visited[j] = 1;
                    break;
                } 
                //If nums2[j] is greater than nums1[i], break out of loop
                else if (nums2[j] > nums1[i]) {
                    break;
                }
                j++;
            }
            i++;
        }
        //Return the final ans
        return ansList;
    }

    main() {
        const nums1 = [1, 2, 3, 3, 4, 5, 6, 7];
        const nums2 = [3, 3, 4, 4, 5, 8];

        // Create an instance of the Solution class
        const finder = new Solution();

        // Get intersection of nums1 and nums2 using class method
        const ans = finder.intersectionArrays(nums1, nums2);

        console.log("Intersection of nums1 and nums2 is:");
        console.log(ans);
    }
}

// Execute main function
new Solution().main();

Complexity Analysis

Time Complexity: O(MxN), where M is the length of nums1 and N is the length of nums2. Space Complexity: O(N), where N is size of nums2, extra space to store answer is not considered.

Intuition

Imagine you're organizing two different parties, and each party has a list of guests. Both lists are sorted alphabetically. The goal is to find out which guests are attending both parties. Starting Point: You have two guest lists:

Party 1: Alice, Bob, Charlie, David

Party 2: Bob, Charlie, Eve, Frank

To efficiently find the common guests, assign one pointer to the first list (Pointer A) and another pointer to the second list (Pointer B), both starting at the top of their respective lists.

Compare the guest at Pointer A with the guest at Pointer B. If they match (for example, both pointers point to Bob), note Bob as a guest attending both parties. After adding Bob, move both pointers forward to the next guests.

If the guest at Pointer A (like Alice) comes before Pointer B (like Bob), you realize Alice isn't at both parties, so move Pointer A to check the next guest. Conversely, if Pointer B points to a guest (like Eve) who comes before Pointer A, move Pointer B forward.

Keep comparing and moving the pointers until one of the pointers reaches the end of its list.

Approach

Declare two pointers, i for iterating through nums1 and j for iterating through nums2, and set both to 0. Initialize a vector or list to hold the intersection results.

Use a while loop to continue the iteration as long as both pointers are within the bounds of their respective arrays.

If the elements at nums1[i] and nums2[j] are equal, add that element to the results and increment both pointers i and j by 1.

If nums1[i] is less than nums2[j], increment pointer i to check the next element in nums1.

If nums2[j] is less than nums1[i], increment pointer j to check the next element in nums2.

This process continues until either pointer exceeds the last index of its respective array. Finally, return the vector containing the intersection.

Dry Run

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    //Function to find intersection of two sorted arrays
    vector<int> intersectionArray(vector<int>& nums1, vector<int>& nums2) {
        // Vector to store the intersection elements
        vector<int> ans;
        // Pointers for nums1 and nums2
        int i = 0, j = 0; 


        // Traverse both arrays using two pointers approach
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums2[j] < nums1[i]) {
                j++;
            } 
          // nums1[i] == nums2[j]
          else { 
                ans.push_back(nums1[i]);
                i++;
                j++;
            }
        }
       
       //Return intersection
        return ans;
    }
};

int main() {
    vector<int> nums1 = {1, 2, 3, 3, 4, 5, 6, 7};
    vector<int> nums2 = {3, 3, 4, 4, 5, 8};

    // Create an instance of the Solution class
    Solution finder;

    // Get intersection of nums1 and nums2 using class method
    vector<int> ans = finder.intersectionArray(nums1, nums2);

    cout << "Intersection of nums1 and nums2 is:" << endl;
    for (int val : ans) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}
import java.util.*;

class Solution {
    // Function to find intersection of two sorted arrays
    public int[] intersectionArray(int[] nums1, int[] nums2) {
        List<Integer> tempList = new ArrayList<>();
        int i = 0, j = 0;

        // Traverse both arrays using two pointers approach
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums2[j] < nums1[i]) {
                j++;
            } 
            // nums1[i] == nums2[j]
            else {
                tempList.add(nums1[i]);
                i++;
                j++;
            }
        }

        // Convert the list to an integer array
        int[] ans = new int[tempList.size()];
        for (int k = 0; k < tempList.size(); k++) {
            ans[k] = tempList.get(k);
        }

        // Return the intersection of two arrays
        return ans;
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 3, 4, 5, 6, 7};
        int[] nums2 = {3, 3, 4, 4, 5, 8};

        // Create an instance of the Solution class
        Solution finder = new Solution();

        // Get intersection of nums1 and nums2 using class method
        int[] ans = finder.intersectionArray(nums1, nums2);

        System.out.println("Intersection of nums1 and nums2 is:");
        for (int val : ans) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}
from typing import List

class Solution:
    #Function to find intersection of two sorted arrays
    def intersectionArray(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # List to store the intersection elements
        ans = []  

         # Pointers for nums1 and nums2
        i, j = 0, 0 

        # Traverse both arrays using two pointers approach
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums2[j] < nums1[i]:
                j += 1
          # nums1[i] == nums2[j]
            else:  
                ans.append(nums1[i])
                i += 1
                j += 1

        return ans

    def main(self):
        # Array Initialization
        nums1 = [1, 2, 3, 3, 4, 5, 6, 7]
        nums2 = [3, 3, 4, 4, 5, 8]

        # Create an instance of the Solution class
        finder = Solution()

        """ Get intersection of nums1 
        and nums2 using class method"""
        ans = finder.intersectionArray(nums1, nums2)

        print("Intersection of nums1 and nums2 is:")

       #Print the intersection of two arrays
        print(ans)

# Execute main function
if __name__ == "__main__":
    Solution().main()
class Solution {
    //Function to find intersection of two sorted arrays
    intersectionArray(nums1, nums2) {
        const ans = [];
        let i = 0, j = 0;

        // Traverse both arrays using two pointers approach
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums2[j] < nums1[i]) {
                j++;
            } 
            // nums1[i] == nums2[j]
             else { 
                 ans.push(nums1[i]);
                  i++;
                  j++;
            }
        }
       //Return final ans
        return ans;
    }

    main() {
        const nums1 = [1, 2, 3, 3, 4, 5, 6, 7];
        const nums2 = [3, 3, 4, 4, 5, 8];

        // Create an instance of the Solution class
        const finder = new Solution();

        // Get intersection of nums1 and nums2 using class method
        const ans = finder.intersectionArray(nums1, nums2);

        console.log("Intersection of nums1 and nums2 is:");
        console.log(ans.join(" "));
    }
}

// Execute main function
new Solution().main();

Complexity Analysis:

Time Complexity: O(M), where M is the length of that array which has less elements. Space Complexity: O(1), extra space to store answer is not considered.

Problem List

Intersection of two sorted arrays

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Dry Run

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code