Why Sorted Input Changes Everything in Array Intersection Problems

Recently, I worked on two different coding problems — one from LeetCode and another from CodeStudio by Coding Ninjas — that both asked for the intersection of two arrays. At first glance, they looked quite similar, but I quickly learned that whether the input arrays are sorted or not changes everything.
In this blog, I’ll walk through the two problems, my thought process, and the simple solutions I implemented without using any fancy data structures like hashmaps.

🧩 Problem 1: Intersection of Two Sorted Arrays (CodeStudio)

🔹 Approach:
Since both arrays were already sorted, I decided to use the two-pointer technique to find common elements efficiently in linear time.

#include <bits/stdc++.h>
vector<int> findArrayIntersection(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
    vector<int> res;
    int i = 0, j = 0;

    while (i < n && j < m) {
        if (arr1[i] == arr2[j]) {
            res.push_back(arr1[i]);
            i++;
            j++;
        }
        else if (arr1[i] < arr2[j]) {
            i++;
        }
        else {
            j++;
        }
    }

    if (res.empty()) {
        res.push_back(-1);
    }

    return res;
}

🧠 Key Insight:
Because the arrays are sorted, we can just walk through them simultaneously and compare elements directly — no need to sort or use extra space.

🧩 Problem 2: Intersection of Two Unsorted Arrays (LeetCode)

🔹 Approach:
Here, the arrays weren’t sorted. So I used a brute-force approach with nested loops. For every element in the first array, I checked for its presence in the second array and added it to the result if found.

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        for(int i = 0; i < nums1.size(); i++){
            int element = nums1[i];
            for(int j = 0; j < nums2.size(); j++){
                if (element == nums2[j]){
                    res.push_back(element);
                    nums2[j] = -1; // mark as visited
                    break;
                }
            }
        }
        return res;
    }
};

🧠 Key Insight:
Since the arrays weren’t sorted, we didn’t have the advantage of two-pointer traversal. Still, by marking visited elements in nums2, I was able to avoid duplicates without using extra space.

🎯 Final Thoughts:

What surprised me most was how the sorted nature of the array entirely changed the optimal approach. Initially, I didn’t even realize one of the problems had sorted arrays — which led me to use a less efficient brute-force method at first.
Lesson learned: Always read the constraints carefully. Sometimes the presence (or absence) of something as simple as sorting can shift your entire approach — from nested loops to linear two-pointer techniques!