algoadvance

Leetcode 2956. Find Common Elements Between Two Arrays

Problem Statement

Given two integer arrays, find all the elements that appear in both arrays. The result should contain duplicates if they appear in both arrays, and it should be sorted. If there are no common elements, return an empty array.

Clarifying Questions

  1. Input Constraints:
    • Can the arrays contain negative numbers?
    • What is the maximum length of the arrays?
    • Will the input arrays be pre-sorted?
  2. Output Format:
    • Should the output be in sorted order?
    • How should duplicates be handled?
  3. Edge Cases:
    • How should the function behave if one or both arrays are empty?
    • What if there are no common elements?

Strategy

  1. Initial Checks:
    • Check if either array is empty. If any array is empty, immediately return an empty list.
  2. Sorting:
    • Sort both arrays if they are not sorted already.
  3. Two-Pointer Technique:
    • Use two pointers to traverse both arrays simultaneously.
    • If elements at both pointers match, add to a result list and move both pointers.
    • If the element in the first array is smaller, move the pointer in the first array.
    • If the element in the second array is smaller, move the pointer in the second array.
  4. Sorting the Result:
    • Although the result will be naturally sorted due to the two-pointer technique, ensure the result is sorted explicitly if needed.
  5. Edge Cases Handling:
    • Address scenarios where arrays are empty or have no common elements.

Code

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> findCommonElements(std::vector<int>& nums1, std::vector<int>& nums2) {
    // If either array is empty, return an empty array
    if(nums1.empty() || nums2.empty())
        return {};

    // Sort both arrays
    std::sort(nums1.begin(), nums1.end());
    std::sort(nums2.begin(), nums2.end());

    std::vector<int> result;
    int i = 0, j = 0;

    // Two-pointer technique to find common elements
    while(i < nums1.size() && j < nums2.size()) {
        if(nums1[i] == nums2[j]) {
            result.push_back(nums1[i]);
            i++;
            j++;
        } else if(nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }

    return result;
}

int main() {
    std::vector<int> nums1 = {1, 2, 2, 3, 4};
    std::vector<int> nums2 = {2, 2, 3, 5};
    std::vector<int> result = findCommonElements(nums1, nums2);

    for (int num : result) {
        std::cout << num << " ";
    }

    return 0;
}

Time Complexity

Edge Cases

  1. Empty Arrays: Both arrays empty, either one empty.
  2. No Common Elements: Arrays with no intersection.
  3. Duplicates: Arrays where elements repeat multiple times.

This reasoning and the code should allow handling both large inputs and typical constraints you might encounter in coding interviews.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI