Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:
answer[0] is a list of all distinct integers in nums1 which are not present in nums2.answer[1] is a list of all distinct integers in nums2 which are not present in nums1.Note that the integers in the lists may be returned in any order.
Example 1:
Input: nums1 = [1,2,3], nums2 = [2,4,6] Output: [[1,3],[4,6]] Explanation: For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3]. For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].
Example 2:
Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2] Output: [[3],[]] Explanation: For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3]. Every integer in nums2 is present in nums1. Therefore, answer[1] = [].
Constraints:
1 <= nums1.length, nums2.length <= 1000-1000 <= nums1[i], nums2[i] <= 1000This approach involves first sorting the data to simplify the problem, allowing for efficient searching or manipulation afterwards. Sorting can often reduce the complexity of further operations by providing a clear ordering of elements.
Depending on the problem's specifics, sorting may allow for easier handling of duplicates or simplification of conditions. Note that the initial overhead of sorting is compensated by the reduced complexity of the subsequent operations.
This C code sorts the array using the quicksort algorithm available through the standard library's qsort function. The compare function helps define the sorting order.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1) if in-place sorting is used.
In this approach, we utilize a HashMap (or a dictionary in languages like Python) to keep track of elements and perform efficient lookups. This is particularly useful when the problem requires checking for existence of elements or handling duplicates.
This approach reduces the time complexity of these operations to O(1) on average, which is significantly faster than scanning through an array.
This C code uses a simple hash table to track occurrences of elements in the array, allowing for O(1) average time complexity for lookups and insertions.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) for iterating through the array.
Space Complexity: O(U), where U is the universe of possible values.
| Approach | Complexity |
|---|---|
| Using Sorting to Solve the Problem | Time Complexity: O(n log n) due to the sorting operation. |
| Using a HashMap for Efficient Lookup | Time Complexity: O(n) for iterating through the array. |
Median of Two Sorted Arrays - Binary Search - Leetcode 4 • NeetCode • 551,948 views views
Watch 9 more video solutions →Practice Find the Difference of Two Arrays with our built-in code editor and test cases.
Practice on FleetCode