Arrays, indices and ranges

A sleeper coach has 72 berths, and a booking program keeps the 12 booked so far in an int[12]. Sort it, and Array.BinarySearch answers “is berth 40 taken?” in 4 comparisons; ask for booked[12] instead and the program throws, because the last index is 11.

Arrays are where every C# collection starts. You will create, fill, sort and search them, lay out a grid as int[,] or int[][], cut parts out of an array with ^ and .. and see which cuts copy, and meet the one array rule that can fail at run time in code that compiles.

An array has a fixed length and starts with default values

new int[8] makes an array of 8 ints, and every one of them is 0 before you store anything. Each element starts with the default value of its type: 0 for numbers, false for bool, null for a string or any other reference. Indexes run from 0 to Length - 1, so a 4-element array has no [4]. A collection expression such as [12, 19, 23, 31] (C# 12) creates an array that already holds its values. Run the basics:

// A coach's fares and bookings in arrays: fixed lengths, default values, and what Resize does.
int[] fares = new int[8];
Console.WriteLine($"new int[8]       Length {fares.Length}, fares[0] = {fares[0]}, fares[7] = {fares[7]}");

string[] names = new string[3];
Console.WriteLine($"new string[3]    names[0] is null: {names[0] is null}");

int[] booked = [12, 19, 23, 31];   // a collection expression (C# 12) makes an int[4]
Console.WriteLine($"booked           [{string.Join(", ", booked)}], indexes 0 to {booked.Length - 1}");

try
{
    Console.WriteLine(booked[4]);
}
catch (IndexOutOfRangeException e)
{
    Console.WriteLine($"booked[4]        {e.GetType().Name}: the last index is 3");
}

// Resize cannot grow an array: it makes a new one, copies, and moves the variable to it.
int[] alias = booked;
Array.Resize(ref booked, 6);
Console.WriteLine($"after Resize     booked [{string.Join(", ", booked)}], Length {booked.Length}");
Console.WriteLine($"                 alias  [{string.Join(", ", alias)}], Length {alias.Length}");
Console.WriteLine($"                 the same array: {ReferenceEquals(alias, booked)}");

Array.Fill(fares, 450);
fares[^1] = 610;
Console.WriteLine($"Fill, then [^1]  [{string.Join(", ", fares)}]");

new int[8]       Length 8, fares[0] = 0, fares[7] = 0
new string[3]    names[0] is null: True
booked           [12, 19, 23, 31], indexes 0 to 3
booked[4]        IndexOutOfRangeException: the last index is 3
after Resize     booked [12, 19, 23, 31, 0, 0], Length 6
                 alias  [12, 19, 23, 31], Length 4
                 the same array: False
Fill, then [^1]  [450, 450, 450, 450, 450, 450, 450, 610]

An array is a reference typereference type: A type whose variables hold a reference to an object, such as a class, string or array. Assigning or passing such a variable copies the reference, so both variables lead to the same object. More in “Value types and reference types”, and its length is fixed when it is made: no method makes an existing array longer. Array.Resize looks as if it does, but the reference documentation says it allocates a new array, copies the elements and replaces the array the variable refers to. Step through the run and watch the two variables:

That is why the run printed Length 6 for booked and Length 4 for alias, and False when it asked whether they were the same array. Array.Fill(fares, 450) set all 8 fares at once, and fares[^1] = 610 changed the last one: ^1 counts one back from the end, as a later section shows.

Sort the array, then BinarySearch halves it at every step

Array.Sort(booked) puts the 12 booked berths in order inside the same array; it returns nothing because it makes no new array. On sorted data, Array.BinarySearch compares the value it looks for with the middle element and drops the half that cannot hold it, which is a binary searchbinary search: A search of sorted values that compares the value it looks for with the middle element and drops the half that cannot hold it, so n values take at most ⌊log₂ n⌋ + 1 comparisons: 4 for 12 values, 20 for a million.. The comparer in this program writes down every element it is asked to compare:

// Berths already booked in a 72-berth coach, in the order people booked them.
int[] booked = [45, 12, 67, 3, 31, 52, 8, 23, 60, 19, 38, 71];

Array.Sort(booked);   // sorts this array in place: no new array
Console.WriteLine($"sorted        [{string.Join(", ", booked)}]");

Console.WriteLine($"search 45  -> {Array.BinarySearch(booked, 45)}");

// A comparer that writes down every value BinarySearch compares with 40.
var probes = new Probes();
int result = Array.BinarySearch(booked, 40, probes);
Console.WriteLine($"search 40  -> {result}, after comparing with {string.Join(", ", probes.Seen)}");
Console.WriteLine($"~{result} = {~result}: 40 would go at index {~result}, in front of {booked[~result]}");

// Insert 40 where the complement says, and the array stays sorted.
int at = ~result;
int[] withForty = [.. booked[..at], 40, .. booked[at..]];
Console.WriteLine($"inserted      [{string.Join(", ", withForty)}]");

// On data that is not sorted, BinarySearch can miss a value that is there.
int[] unsorted = [45, 12, 67, 3, 31];
Console.WriteLine($"unsorted: BinarySearch(3) -> {Array.BinarySearch(unsorted, 3)}, IndexOf(3) -> {Array.IndexOf(unsorted, 3)}");

sealed class Probes : IComparer<int>
{
    public List<int> Seen { get; } = [];

    // BinarySearch calls Compare(element, value) once for each element it looks at.
    public int Compare(int element, int value)
    {
        Seen.Add(element);
        return element.CompareTo(value);
    }
}

sorted        [3, 8, 12, 19, 23, 31, 38, 45, 52, 60, 67, 71]
search 45  -> 7
search 40  -> -8, after comparing with 31, 52, 38, 45
~-8 = 7: 40 would go at index 7, in front of 45
inserted      [3, 8, 12, 19, 23, 31, 38, 40, 45, 52, 60, 67, 71]
unsorted: BinarySearch(3) -> -1, IndexOf(3) -> 3

Searching for 45 returned its index, 7. Searching for 40 returned −8, after comparing with 31, 52, 38 and 45. A negative result means “not there”, and its bitwise complement, ~(-8), is 7: the index of the first element larger than 40, where 40 must go to keep the array sorted. The program inserted it there. Step through the same search on the same 12 values and watch the range shrink:

When the range is empty, lo stops at 7, the same 7 that ~(-8) gave. Each probe halves what is left, so 12 values take at most 4 probes, and a million take at most 20. The last line of the run is the trap: on the unsorted [45, 12, 67, 3, 31], BinarySearch(3) returned −1 although 3 is at index 3, because after 67 and 45 it had dropped the positions where 3 sat. Array.IndexOf checks every element in turn, so it works on any order, at the cost of a full scan.

A grid is one block of values or an array of rows

A chair-car coach is a grid of rows and seats, and C# gives it two shapes. A multidimensional arraymultidimensional array: An array with more than one index, such as int[3, 4], read as seats[row, seat]. It is one object with every row the same length; Length counts all its elements and GetLength(d) gives the length of dimension d., int[3, 4], is one object with the same 4 seats in every row, read as seats[row, seat]. A jagged arrayjagged array: An array whose elements are arrays, such as int[][], read as bays[row][berth]. Each row is an array of its own, may have its own length, and is null until it is created., int[3][], is an array whose elements are arrays, read as bays[row][berth], and each row may have its own length, as a sleeper coach’s last bay of 2 side berths does:

using System.Globalization;

// A chair-car coach as a grid of 3 rows and 4 seats: 0 is free, 1 is booked.
int[,] seats = new int[3, 4];
seats[0, 1] = 1;
seats[2, 3] = 1;
Console.WriteLine($"int[3, 4]   Rank {seats.Rank}, Length {seats.Length}, GetLength(0) {seats.GetLength(0)}, GetLength(1) {seats.GetLength(1)}");
Console.Write("foreach     ");
foreach (int seat in seats)
{
    Console.Write(seat);   // row 0 first, then row 1, then row 2
}
Console.WriteLine();

// A sleeper coach as a jagged array: each bay is its own array, of any length.
int[][] bays = new int[3][];
Console.WriteLine($"int[3][]    bays[0] is null until it is created: {bays[0] is null}");
bays[0] = new int[8];   // a bay with 8 berths
bays[1] = new int[8];
bays[2] = new int[2];   // the 2 side berths at the end
bays[2][1] = 1;
Console.WriteLine($"bays        Length {bays.Length}; rows of {bays[0].Length}, {bays[1].Length} and {bays[2].Length}; bays[2][1] = {bays[2][1]}");

// What each layout allocates for a million ints.
long before = GC.GetAllocatedBytesForCurrentThread();
int[,] block = new int[1000, 1000];
long blockBytes = GC.GetAllocatedBytesForCurrentThread() - before;

before = GC.GetAllocatedBytesForCurrentThread();
int[][] rows = new int[1000][];
for (int i = 0; i < rows.Length; i++)
{
    rows[i] = new int[1000];
}
long rowBytes = GC.GetAllocatedBytesForCurrentThread() - before;

CultureInfo inv = CultureInfo.InvariantCulture;
Console.WriteLine($"int[1000, 1000]          1 object      {blockBytes.ToString("N0", inv),10} bytes");
Console.WriteLine($"int[1000][] with rows    1,001 objects {rowBytes.ToString("N0", inv),10} bytes");
GC.KeepAlive(block);
GC.KeepAlive(rows);

int[3, 4]   Rank 2, Length 12, GetLength(0) 3, GetLength(1) 4
foreach     010000000001
int[3][]    bays[0] is null until it is created: True
bays        Length 3; rows of 8, 8 and 2; bays[2][1] = 1
int[1000, 1000]          1 object       4,000,040 bytes
int[1000][] with rows    1,001 objects  4,032,024 bytes

Step through how each one sits in memory:

Length means different things in the two: all 12 seats of the int[3, 4], but only the 3 rows of the jagged array. The table sums up the differences the run showed:

Choose by the data: a board or an image whose rows always match fits int[,], while rows that differ, or rows you pass to a method one at a time, fit int[][]. The extra memory of the jagged form was under 1 % here.

A range copies an array, and a span slice shares it

An index from the endindex from end: An index written with ^, such as ^1, that counts back from the end of a string, array or span: ^1 is the last element, ^2 the one before it, and ^0 the position just past the end. More in “Strings: slicing, immutability and comparison” such as fares[^1] is the last element, and a rangerange: Two indexes written a..b, such as s[4..8]: the part of a string, array or span from index a up to, but not including, index b. Either end may be left out, as in s[..3] or s[^2..]. More in “Strings: slicing, immutability and comparison” such as fares[1..4] is the elements from index 1 up to, but not including, index 4. On an array, the language specification says a range is a new array that holds a copy of those elements. A spanspan: A Span<T> or ReadOnlySpan<T>: a view of a run of values that sit next to each other in memory, such as part of an array, which reads and writes them where they are. array.AsSpan(1, 3) refers to three elements of array and copies nothing. is different: fares.AsSpan()[1..4] is a view of the same three elements, with no array of its own. This program changes fares after taking both slices:

// Fares of six trains on one route, from the cheapest to the dearest.
int[] fares = [450, 520, 610, 700, 880, 990];
Console.WriteLine($"fares[^1] = {fares[^1]}, fares[^2] = {fares[^2]}, fares[1..4] = [{string.Join(", ", fares[1..4])}]");

int[] copy = fares[1..4];               // a range on an array: a new array of 3
Span<int> view = fares.AsSpan()[1..4];  // a range on a span: the same 3 elements of fares

fares[1] = 555;
Console.WriteLine($"after fares[1] = 555    copy[0] = {copy[0]}, view[0] = {view[0]}");
view[2] = 777;
Console.WriteLine($"after view[2] = 777     fares[3] = {fares[3]}, copy[2] = {copy[2]}");

// What 1,000 slices of 100 values each cost.
int[] prices = new int[1_100];
long sum = 0;
long before = GC.GetAllocatedBytesForCurrentThread();
for (int i = 0; i < 1_000; i++)
{
    int[] window = prices[i..(i + 100)];
    sum += window[0];
}
long rangeBytes = GC.GetAllocatedBytesForCurrentThread() - before;

before = GC.GetAllocatedBytesForCurrentThread();
for (int i = 0; i < 1_000; i++)
{
    ReadOnlySpan<int> window = prices.AsSpan(i, 100);
    sum += window[0];
}
long spanBytes = GC.GetAllocatedBytesForCurrentThread() - before;
Console.WriteLine($"1,000 array ranges: {rangeBytes} bytes; 1,000 span slices: {spanBytes} bytes (sum {sum})");

// An Index and a Range are values you can store and pass around.
Index last = ^1;
Range inner = 1..^1;
Console.WriteLine($"fares[last] = {fares[last]}, fares[inner].Length = {fares[inner].Length}");
try
{
    Console.WriteLine(fares[^0]);
}
catch (IndexOutOfRangeException e)
{
    Console.WriteLine($"fares[^0]: {e.GetType().Name}, because ^0 is one past the last element");
}

fares[^1] = 990, fares[^2] = 880, fares[1..4] = [520, 610, 700]
after fares[1] = 555    copy[0] = 520, view[0] = 555
after view[2] = 777     fares[3] = 777, copy[2] = 700
1,000 array ranges: 424000 bytes; 1,000 span slices: 0 bytes (sum 0)
fares[last] = 990, fares[inner].Length = 4
fares[^0]: IndexOutOfRangeException, because ^0 is one past the last element

Step through it and watch which slice follows the change:

copy[0] stayed 520 when fares[1] became 555, while view[0] read 555, and writing view[2] = 777 changed fares[3]. The cost follows from the same rule: 1,000 ranges of 100 ints allocated 424,000 bytes, each a new array of 24 + 400 bytes, and 1,000 span slices allocated nothing. Index and Range are types, so ^1 and 1..^1 can be stored in variables, and ^0 is one past the last element, which is why fares[^0] threw.

Arrays are covariant, so a store can fail at run time

A string[] of station codes can be assigned to a variable of type object[], because a string is an object. This rule is array covariancearray covariance: The rule that lets an array of one reference type be used as an array of a base type, such as a string[] as an object[]. The array keeps its real element type, so storing a value of another type through it throws ArrayTypeMismatchException., and Microsoft’s guide to variance warns that it is not type safe: the array is still a string[], whatever the variable says. Watch what happens when the program stores a number through the object[]:

// Station codes in a string[], seen through a variable of type object[].
string[] stations = ["NDLS", "MAS", "HWH"];
object[] items = stations;   // compiles: array covariance
Console.WriteLine($"items refers to a {items.GetType().Name}");

items[0] = "SBC";            // a string: the store succeeds
Console.WriteLine($"stations[0] is now {stations[0]}");

try
{
    items[1] = 42;           // compiles, but the array can only hold strings
}
catch (ArrayTypeMismatchException e)
{
    Console.WriteLine($"items[1] = 42 -> {e.GetType().Name}; stations[1] is still {stations[1]}");
}

// A read-only interface is covariant as well, and it has no way to store anything.
IReadOnlyList<object> readOnly = stations;
Console.WriteLine($"IReadOnlyList<object>: Count {readOnly.Count}, [2] = {readOnly[2]}");

// object[] boxes = new int[3]; does not compile: arrays of value types are not covariant.
object[] boxes = [1, 2, 3];  // an object[] that holds three boxed ints
Console.WriteLine($"an object[] of {boxes[0].GetType().Name} values accepts a string: {Store(boxes, "four")}");

static bool Store(object[] array, object value)
{
    array[0] = value;
    return true;
}

items refers to a String[]
stations[0] is now SBC
items[1] = 42 -> ArrayTypeMismatchException; stations[1] is still MAS
IReadOnlyList<object>: Count 3, [2] = HWH
an object[] of Int32 values accepts a string: True

Storing "SBC" worked and changed stations[0], because it is the same array. Storing 42 compiled, then threw ArrayTypeMismatchException, and stations[1] stayed MAS. The language specification explains why: because of covariance, every store into an array of a reference type is checked at run time against the array’s real element type. The rule does not reach value types, so object[] boxes = new int[3]; does not compile, and the object[] of boxed ints at the end is an array of objects that accepts any value.

Practise: rotate a seat map

rotate.cs checks a method that you write. Rotate turns a seat map 90 degrees clockwise and returns it as a jagged array: row r of the result is column r of the grid, read from its bottom row up. The checks include a square grid, a 2 × 3 grid, a single row and an empty grid. The method you start from only throws, so all 6 checks fail:

// Practice: write Rotate so that every check below passes, then run this file again.
// Rotate turns a seat map 90 degrees clockwise and returns it as a jagged array:
// row r of the result is column r of the grid, read from its bottom row up.
(string Name, int[,] Grid, int[][] Expected)[] checks =
[
    ("1 x 1", new int[,] { { 7 } }, [[7]]),
    ("2 x 2", new int[,] { { 1, 2 }, { 3, 4 } }, [[3, 1], [4, 2]]),
    ("3 x 3", new int[,] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }, [[7, 4, 1], [8, 5, 2], [9, 6, 3]]),
    ("2 x 3", new int[,] { { 1, 2, 3 }, { 4, 5, 6 } }, [[4, 1], [5, 2], [6, 3]]),
    ("1 x 4", new int[,] { { 1, 2, 3, 4 } }, [[1], [2], [3], [4]]),
    ("0 x 0", new int[0, 0], []),
];

int passed = 0;
foreach (var (name, grid, expected) in checks)
{
    string verdict;
    try
    {
        int[][] got = Rotate(grid);
        verdict = Same(got, expected) ? "ok" : $"FAIL, returned {Show(got)}";
    }
    catch (Exception e)
    {
        verdict = $"FAIL, {e.GetType().Name}";
    }
    if (verdict == "ok")
    {
        passed++;
    }
    Console.WriteLine($"Rotate({name}): {verdict}");
}
Console.WriteLine($"{passed} of {checks.Length} checks pass");
return passed == checks.Length ? 0 : 1;

static int[][] Rotate(int[,] grid)
{
    throw new NotImplementedException("Make GetLength(1) rows; fill row r from column r, bottom row first.");
}

static bool Same(int[][] a, int[][] b)
{
    if (a.Length != b.Length)
    {
        return false;
    }
    for (int r = 0; r < a.Length; r++)
    {
        if (!a[r].AsSpan().SequenceEqual(b[r]))
        {
            return false;
        }
    }
    return true;
}

static string Show(int[][] g) => "[" + string.Join(", ", g.Select(row => "[" + string.Join(", ", row) + "]")) + "]";

Rotate(1 x 1): FAIL, NotImplementedException
Rotate(2 x 2): FAIL, NotImplementedException
Rotate(3 x 3): FAIL, NotImplementedException
Rotate(2 x 3): FAIL, NotImplementedException
Rotate(1 x 4): FAIL, NotImplementedException
Rotate(0 x 0): FAIL, NotImplementedException
0 of 6 checks pass

Then check yourself on default values, the complement of a missed search, the two grids, the copy against the view and the covariant store. The session opens with the idea you have got wrong most often and explains every choice:

Interview questions

Fresher · What is the difference between int[,] and int[][] in C#?

int[,] is a rectangular, multidimensional array: one object that holds every element in one block, with the same length in every row, read as grid[row, column]. int[][] is a jagged array: an array of references to row arrays, read as grid[row][column], where each row is its own object, may have its own length and is null until you create it. Length counts every element of an int[,] (12 for int[3, 4]) but only the rows of an int[][], so use GetLength(0) and GetLength(1) for the dimensions of the rectangular one. A jagged array can hand one row to a method as an int[] and supports ranges; a multidimensional array supports neither. For a million ints, the block was one object of 4,000,040 bytes and the rows of rows 1,001 objects of 4,032,024 bytes.

Key takeaways

• An array’s length is fixed when it is made and every element starts at its default value; Array.Resize makes a new array and moves only the variable passed with ref.
• Array.Sort sorts in place, and Array.BinarySearch is right only on sorted data, returning the complement of the insertion index when the value is missing.
• int[,] is one block with equal rows and Length counting every element; int[][] is an array of row arrays of any length, each null until created.
• ^1 is the last element and a..b stops before b; a range on an array is a copy, while a span slice is a view of the same elements that allocates nothing.
• Array covariance lets a string[] pass as an object[], and a store of the wrong type through it throws ArrayTypeMismatchException at run time.