Question

How to find the intersection of two arrays (values that exist in both arrays) in Pascal

Answer 1

program ArrayIntersection;

{$mode objfpc}{$H+}

uses
  SysUtils, FGL; // FGL provides clean, reliable native generics in FPC

type
  TIntArray = array of Integer;
  
  // FGL uses TFPGMap for key-value maps
  TIntBoolMap = specialize TFPGMap<Integer, Boolean>;

{-------------------------------------------------------------------------------
  Finds the unique intersection of two integer arrays.
-------------------------------------------------------------------------------}
function FindArrayIntersection(const Arr1, Arr2: TIntArray): TIntArray;
var
  SeenMap: TIntBoolMap;
  I, Index, ResultCount: Integer;
begin
  // Optimize: Hash/map the smaller array to minimize memory overhead
  if Length(Arr1) > Length(Arr2) then
    Exit(FindArrayIntersection(Arr2, Arr1));

  SeenMap := TIntBoolMap.Create;
  // Enable sorted key lookups for fast binary searching (O(log N))
  SeenMap.Sorted := True;
  
  // Allocate max possible memory for output array upfront
  SetLength(Result, Length(Arr1));
  ResultCount := 0;

  try
    // Step 1: Populate map with unique keys from Arr1
    for I := 0 to High(Arr1) do
    begin
      if not SeenMap.Find(Arr1[I], Index) then
        SeenMap.Add(Arr1[I], True);
    end;

    // Step 2: Iterate through Arr2 and match elements
    for I := 0 to High(Arr2) do
    begin
      // Find returns True if key exists and populates Index
      if SeenMap.Find(Arr2[I], Index) then
      begin
        Result[ResultCount] := Arr2[I];
        Inc(ResultCount);
        SeenMap.Delete(Index); // Remove to prevent duplicate matches from Arr2
      end;
    end;

    // Step 3: Trim array to actual match count
    SetLength(Result, ResultCount);

  finally
    SeenMap.Free;
  end;
end;

procedure PrintArray(const LabelText: string; const Arr: TIntArray);
var
  I: Integer;
begin
  Write(LabelText, ' [');
  for I := 0 to High(Arr) do
  begin
    Write(Arr[I]);
    if I < High(Arr) then
      Write(', ');
  end;
  Writeln(']');
end;

var
  Arr1, Arr2, Intersection: TIntArray;
begin
  Arr1 := TIntArray.Create(5, 7, 1, 1, 3, 0, 6, 2);
  Arr2 := TIntArray.Create(2, 8, 8, 6, 9, 3, 3, 4, 4);

  PrintArray('Arr1:        ', Arr1);
  PrintArray('Arr2:        ', Arr2);

  Intersection := FindArrayIntersection(Arr1, Arr2);

  PrintArray('Intersection:', Intersection); // Output: [2, 6, 3]
end.


{
run:

Arr1:         [5, 7, 1, 1, 3, 0, 6, 2]
Arr2:         [2, 8, 8, 6, 9, 3, 3, 4, 4]
Intersection: [2, 6, 3]


}

 

70+ SQL courses for beginners and professionals