program MergeSortedArrays;
{$mode objfpc}
uses
SysUtils;
type
TIntArray = array of Integer;
{
Merges two sorted arrays into a new sorted array without duplicates.
Example:
Arr1 = [1, 2, 2, 3, 7, 7, 7, 8, 9]
Arr2 = [0, 0, 4, 4, 4, 5, 6, 7, 7, 8]
Result:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Time Complexity: O(N + M)
Space Complexity: O(N + M)
}
function MergeSortedUnique(const Arr1, Arr2: TIntArray): TIntArray;
var
I, J, K: Integer;
Value: Integer;
begin
I := 0;
J := 0;
K := 0;
Result := nil; // Initialize dynamic array
{ Allocate the maximum possible size }
SetLength(Result, Length(Arr1) + Length(Arr2));
while (I < Length(Arr1)) and (J < Length(Arr2)) do
begin
if Arr1[I] < Arr2[J] then
begin
Value := Arr1[I];
Inc(I);
end
else if Arr1[I] > Arr2[J] then
begin
Value := Arr2[J];
Inc(J);
end
else
begin
{ Same value exists in both arrays }
Value := Arr1[I];
Inc(I);
Inc(J);
end;
{ Add only if different from the previously added value }
if (K = 0) or (Result[K - 1] <> Value) then
begin
Result[K] := Value;
Inc(K);
end;
end;
{ Process remaining elements from Arr1 }
while I < Length(Arr1) do
begin
Value := Arr1[I];
Inc(I);
if (K = 0) or (Result[K - 1] <> Value) then
begin
Result[K] := Value;
Inc(K);
end;
end;
{ Process remaining elements from Arr2 }
while J < Length(Arr2) do
begin
Value := Arr2[J];
Inc(J);
if (K = 0) or (Result[K - 1] <> Value) then
begin
Result[K] := Value;
Inc(K);
end;
end;
{ Resize to actual number of elements }
SetLength(Result, K);
end;
procedure PrintArray(const Arr: TIntArray);
var
I: Integer;
begin
Write('[');
for I := 0 to High(Arr) do
begin
Write(Arr[I]);
if I < High(Arr) then
Write(', ');
end;
Writeln(']');
end;
var
Arr1, Arr2, Merged: TIntArray;
begin
Arr1 := TIntArray.Create(1, 2, 2, 3, 7, 7, 7, 8, 9);
Arr2 := TIntArray.Create(0, 0, 4, 4, 4, 5, 6, 7, 7, 8);
Merged := MergeSortedUnique(Arr1, Arr2);
Write('Result: ');
PrintArray(Merged);
end.
{
run:
Result: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
}
