program NSmallest2DArray;
{$mode objfpc}{$H+}{$MODESWITCH ADVANCEDRECORDS}
uses
SysUtils, Math;
type
{ Dynamic array type definitions for clarity and flexibility }
T1DIntArray = array of Integer;
T2DIntArray = array of array of Integer;
{
Bounded Max-Heap data structure.
Used to track the N smallest elements encountered so far.
The largest element among the current N smallest sits at the root (index 0),
allowing O(1) comparison and O(log N) updates when a smaller value is found.
}
TBoundedMaxHeap = record
private
FItems: T1DIntArray;
FCapacity: Integer;
FCount: Integer;
procedure SiftUp(Index: Integer);
procedure SiftDown(Index: Integer);
procedure Swap(I, J: Integer);
public
procedure Initialize(ACapacity: Integer);
procedure PushOrReplace(Value: Integer);
function ExtractSortedAscending: T1DIntArray;
property MaxValue: Integer read FItems[0];
property Count: Integer read FCount;
end;
{ TBoundedMaxHeap Implementation }
procedure TBoundedMaxHeap.Swap(I, J: Integer);
var
Temp: Integer;
begin
Temp := FItems[I];
FItems[I] := FItems[J];
FItems[J] := Temp;
end;
procedure TBoundedMaxHeap.Initialize(ACapacity: Integer);
begin
FCapacity := ACapacity;
FCount := 0;
SetLength(FItems, FCapacity);
end;
procedure TBoundedMaxHeap.SiftUp(Index: Integer);
var
Parent: Integer;
begin
while Index > 0 do
begin
Parent := (Index - 1) div 2;
if FItems[Index] > FItems[Parent] then
begin
Swap(Index, Parent);
Index := Parent;
end
else
Break;
end;
end;
procedure TBoundedMaxHeap.SiftDown(Index: Integer);
var
LeftChild, RightChild, MaxChild: Integer;
begin
while (2 * Index + 1) < FCount do
begin
LeftChild := 2 * Index + 1;
RightChild := 2 * Index + 2;
MaxChild := LeftChild;
if (RightChild < FCount) and (FItems[RightChild] > FItems[LeftChild]) then
MaxChild := RightChild;
if FItems[MaxChild] > FItems[Index] then
begin
Swap(Index, MaxChild);
Index := MaxChild;
end
else
Break;
end;
end;
procedure TBoundedMaxHeap.PushOrReplace(Value: Integer);
begin
if FCapacity <= 0 then Exit;
{ If heap is not full, append and sift up }
if FCount < FCapacity then
begin
FItems[FCount] := Value;
Inc(FCount);
SiftUp(FCount - 1);
end
{ If full and incoming value is smaller than current max, replace root }
else if Value < FItems[0] then
begin
FItems[0] := Value;
SiftDown(0);
end;
end;
function TBoundedMaxHeap.ExtractSortedAscending: T1DIntArray;
var
I, OriginalCount: Integer;
begin
SetLength(Result, FCount);
OriginalCount := FCount;
{ Pop items from Max-Heap into the array from back to front }
for I := OriginalCount - 1 downto 0 do
begin
Result[I] := FItems[0];
FItems[0] := FItems[FCount - 1];
Dec(FCount);
SiftDown(0);
end;
end;
{
Finds the N smallest elements in a 2D integer array.
Time Complexity: O(R * C * log N) where R is rows and C is columns.
Space Complexity: O(N) auxiliary space for the bounded heap.
}
function FindNSmallest(const Matrix: T2DIntArray; N: Integer): T1DIntArray;
var
Heap: TBoundedMaxHeap;
Row, Col, TotalElements: Integer;
begin
{ Edge cases: empty matrix or non-positive N }
if (Length(Matrix) = 0) or (N <= 0) then
begin
SetLength(Result, 0);
Exit;
end;
{ Count total elements across all rows }
TotalElements := 0;
for Row := 0 to High(Matrix) do
Inc(TotalElements, Length(Matrix[Row]));
{ Clamp N to the total number of available elements }
N := Min(N, TotalElements);
Heap.Initialize(N);
{ Process every element in the 2D array }
for Row := 0 to High(Matrix) do
begin
for Col := 0 to High(Matrix[Row]) do
begin
Heap.PushOrReplace(Matrix[Row][Col]);
end;
end;
{ Extract elements into ascending sorted order }
Result := Heap.ExtractSortedAscending;
end;
{ Helper procedure to display a 1D array }
procedure Print1DArray(const Arr: T1DIntArray);
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;
{ Helper procedure to display a 2D matrix }
procedure Print2DArray(const Matrix: T2DIntArray);
var
Row, Col: Integer;
begin
for Row := 0 to High(Matrix) do
begin
Write(' [');
for Col := 0 to High(Matrix[Row]) do
begin
Write(Matrix[Row][Col]:4);
if Col < High(Matrix[Row]) then
Write(',');
end;
Writeln(' ]');
end;
end;
var
Grid: T2DIntArray;
Smallest: T1DIntArray;
N: Integer;
begin
{ Initialize a sample 2D array (4x4) }
SetLength(Grid, 4, 4);
Grid[0][0] := 42; Grid[0][1] := 12; Grid[0][2] := 85; Grid[0][3] := 3;
Grid[1][0] := 7; Grid[1][1] := 99; Grid[1][2] := 15; Grid[1][3] := 23;
Grid[2][0] := 64; Grid[2][1] := 1; Grid[2][2] := 18; Grid[2][3] := 30;
Grid[3][0] := 3; Grid[3][1] := 55; Grid[3][2] := 11; Grid[3][3] := 90;
Writeln('Input Matrix:');
Print2DArray(Grid);
Writeln;
N := 5;
Writeln(Format('Finding the %d smallest values:', [N]));
Smallest := FindNSmallest(Grid, N);
Print1DArray(Smallest);
end.
(*
run:
Input Matrix:
[ 42, 12, 85, 3 ]
[ 7, 99, 15, 23 ]
[ 64, 1, 18, 30 ]
[ 3, 55, 11, 90 ]
Finding the 5 smallest values:
[1, 3, 3, 7, 11]
*)
