4. Array programs

// Second largest (distinct) — single pass O(n)
static int? SecondLargest(int[] a)
{
    int? first = null, second = null;
    foreach (var n in a)
    {
        if (first is null || n > first) { second = first; first = n; }
        else if (n != first && (second is null || n > second)) second = n;
    }
    return second;
}

// Find duplicates — HashSet O(n)
static List<int> Duplicates(int[] a)
{
    var seen = new HashSet<int>(); var dups = new HashSet<int>();
    foreach (var n in a) if (!seen.Add(n)) dups.Add(n);
    return dups.ToList();
}

// Missing number in 1..n — sum formula O(n), O(1) space
static int Missing(int[] a, int n) => n * (n + 1) / 2 - a.Sum();

// Move zeros to the end keeping order — O(n), in place
static void MoveZeros(int[] a)
{
    int write = 0;
    foreach (var n in a) if (n != 0) a[write++] = n;
    while (write < a.Length) a[write++] = 0;
}

// Rotate array right by k — reverse trick O(n), O(1)
static void Rotate(int[] a, int k)
{
    k %= a.Length;
    Array.Reverse(a); Array.Reverse(a, 0, k); Array.Reverse(a, k, a.Length - k);
}

// Merge two sorted arrays — O(n + m)
static int[] Merge(int[] x, int[] y)
{
    var r = new int[x.Length + y.Length]; int i = 0, j = 0, k = 0;
    while (i < x.Length && j < y.Length) r[k++] = x[i] <= y[j] ? x[i++] : y[j++];
    while (i < x.Length) r[k++] = x[i++];
    while (j < y.Length) r[k++] = y[j++];
    return r;
}