Repeated Intersections

The Problem

Given two integer arrays arr1 and arr2, return an array containing all elements that appear in both arrays, including duplicates. An element that appears p times in arr1 and q times in arr2 should appear min(p, q) times in the result.

arr1 = [1, 2, 2, 3],  arr2 = [2, 2, 3, 3]  →  [2, 2, 3]
arr1 = [1, 2, 3],     arr2 = [4, 5, 6]      →  []
arr1 = [2, 2, 2],     arr2 = [2, 2]          →  [2, 2]
arr1 = [1, 2, 3],     arr2 = [1, 2, 3]       →  [1, 2, 3]

Examples

Example 1

Input:  arr1 = [1, 2, 2, 3],  arr2 = [2, 2, 3, 3]
Output: [2, 2, 3]
Explanation: 2 appears twice in both → 2 appears twice in result.
             3 appears once in arr1, twice in arr2 → min(1,2)=1 → once in result.

Example 2

Input:  arr1 = [2, 2, 2],  arr2 = [2, 2]
Output: [2, 2]
Explanation: 2 appears 3 times in arr1, 2 times in arr2 → min(3,2)=2 appearances.

Example 3

Input:  arr1 = [1, 3, 5],  arr2 = [2, 4, 6]
Output: []
Explanation: No common values exist.

Intuition

This is nearly identical to Unique Intersections — but with one critical difference: every matching pair is recorded, not just the first one.

On a sorted array, when arr1[i] == arr2[j], both pointers are sitting on the same value. That’s one instance of a common element. Record it and advance both. If the next positions also match, that’s another shared instance — record again. The min(p, q) rule falls out naturally: once the shorter side runs out of copies of a value, the pointers stop matching and move on.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Sort["Sort arr1 and arr2"]
  Init(["i = 0, j = 0, result = []"])
  Check{"i < len(arr1)<br/>AND j < len(arr2)?"}
  Cmp{"arr1[i] vs arr2[j]"}
  Match["result.append(arr1[i])<br/>i += 1,  j += 1"]
  AdvI["i += 1"]
  AdvJ["j += 1"]
  Done(["return result"])

  Sort --> Init --> Check
  Check -->|"yes"| Cmp
  Cmp -->|"equal — record every match"| Match --> Check
  Cmp -->|"arr1[i] < arr2[j]"| AdvI --> Check
  Cmp -->|"arr1[i] > arr2[j]"| AdvJ --> Check
  Check -->|"no"| Done

Repeated Intersections — identical to Unique Intersections but every match is recorded unconditionally. The min(p, q) rule emerges naturally from both pointers advancing on each match.

Solution

from typing import List

class Solution:
    def repeated_intersections(self, arr1: List[int], arr2: List[int]) -> List[int]:
        # Sort both arrays to enable simultaneous traversal
        arr1.sort()
        arr2.sort()

        result = []
        # Initialize pointers at the start of each array
        i = 0
        j = 0

        # Main loop: run while both arrays have unprocessed elements
        while i < len(arr1) and j < len(arr2):
            if arr1[i] == arr2[j]:
                # Common element found — record every match, duplicates included
                result.append(arr1[i])
                # Advance both pointers to look for the next shared element
                i += 1
                j += 1
            elif arr1[i] < arr2[j]:
                # arr1's element is smaller — no match possible at this position
                i += 1
            else:
                # arr2's element is smaller — no match possible at this position
                j += 1

        return result


sol = Solution()
print(sol.repeated_intersections([1, 2, 2, 3], [2, 2, 3, 3]))    # [2, 2, 3]
print(sol.repeated_intersections([2, 2, 2], [2, 2]))              # [2, 2]
print(sol.repeated_intersections([1, 3, 5], [2, 4, 6]))           # []
print(sol.repeated_intersections([1, 2, 3], [1, 2, 3]))           # [1, 2, 3]
print(sol.repeated_intersections([], [1, 2]))                     # []

Dry Run — Example 1

arr1 = [1, 2, 2, 3], arr2 = [2, 2, 3, 3] (both already sorted)

i=0, j=0, result=[]

Step 1 │ arr1[0]=1, arr2[0]=2 │ 1 < 2 → advance i                │ i=1, j=0
Step 2 │ arr1[1]=2, arr2[0]=2 │ 2 == 2 → record 2                │ i=2, j=1,  result=[2]
Step 3 │ arr1[2]=2, arr2[1]=2 │ 2 == 2 → record 2 again          │ i=3, j=2,  result=[2,2]
Step 4 │ arr1[3]=3, arr2[2]=3 │ 3 == 3 → record 3                │ i=4, j=3,  result=[2,2,3]

i=4 == len(arr1)=4 → loop exits

Result: [2, 2, 3] ✓

Compare with Unique Intersections: in step 3, Unique would have checked
result[-1]==2 and skipped. Repeated does not check — it records unconditionally.
That single difference is the entire distinction between the two problems.

Why min(p, q) Falls Out Naturally

You don’t need to count occurrences of each value. The simultaneous pointer movement handles it automatically:

• Each match consumes one copy from arr1 (i advances) and one copy from arr2 (j advances).
• The side with fewer copies runs out of them first. When it does, arr1[i] ≠ arr2[j] again, and the match streak ends.
• The number of consecutive matches is exactly min(p, q) — the count of the shorter side.

For arr1 = [2, 2, 2] and arr2 = [2, 2]:

• Match at i=0, j=0 → record, i=1, j=1
• Match at i=1, j=1 → record, i=2, j=2
• j=2 == len(arr2) → loop exits. Two matches recorded = min(3, 2) = 2 ✓

Unique vs Repeated — The One-Line Difference

The only structural difference is the guard condition on the append. Remove it, and Unique Intersections becomes Repeated Intersections.

Complexity Analysis

Edge Cases

Key Takeaway

Repeated Intersections is Unique Intersections without the duplicate guard — one line removed, and the semantics shift from set intersection to multiset intersection. The min(p, q) count falls out naturally from two pointers advancing together: each match consumes one copy from each side, and the smaller side dictates how many total matches occur.