Category 13

Intervals, Matrix & Miscellaneous

Master interval merging, matrix transformations, and two-pointer techniques on sorted structures. Learn sweep-line algorithms, elegant rotation patterns, and how to solve geometric problems on grids. Advanced pattern recognition across diverse problem domains.

Problems

Difficulty Levels

100%

Complete Solutions

Codility Problems

Theory

Interval Merging & Matrix Patterns

Interval problems form a core algorithmic domain. Master sorting strategies, greedy selection, and boundary handling. Matrix problems require careful index management and pattern visualization.

1. Interval Merging Patterns

Sort by start: Sort intervals by start point. Merge overlapping intervals by comparing current start with last end. Track merged result in list.

Key insight: [1,3] and [2,6] overlap because 2 ≤ 3. Merge to [1,6]. Non-overlapping: start > prev_end.

2. Greedy Interval Selection

Non-overlapping selection: Sort by end point, greedily select intervals that don't overlap with previous. Maximizes count of non-overlapping intervals.

3. Matrix Layer Peeling

Spiral/layer approach: Process matrix in concentric layers. Track top, bottom, left, right boundaries. Shrink after each side traversal. Avoid re-processing.

4. Matrix Rotation Technique

Transpose + reverse: Rotate 90° clockwise: transpose matrix (swap M[i][j] with M[j][i]), then reverse each row. Elegant and cache-friendly.

5. Two-Pointer on Sorted Data

Caterpillar method: For problems on sorted arrays, use two pointers moving in coordinated fashion. Useful for counting triangles, detecting overlaps.

Problems

1. Merge Intervals (LC 56)

Given an array of intervals [start, end], merge all overlapping intervals and return non-overlapping result.

Medium Interval Merging O(n log n)

Input

[[1,3],[2,6],[8,10],[15,18]]

Output

[[1,6],[8,10],[15,18]]

Time

O(n log n)

Space

O(n)

Approach

Sort intervals by start point. Use Array.Sort with custom comparator.

Iterate through sorted intervals. If current start ≤ last end, merge by extending last end. Else, add new interval.

Return merged list. Convert to array if needed.

Code Solution (C#)

csharp

public int[][] Merge(int[][] intervals) {
    Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

    var merged = new List<int[]>();
    int curStart = intervals[0][0];
    int curEnd = intervals[0][1];

    for (int i = 1; i < intervals.Length; i++) {
        int start = intervals[i][0];
        int end = intervals[i][1];

        if (start <= curEnd) {
            curEnd = Math.Max(curEnd, end);
        } else {
            merged.Add(new int[] { curStart, curEnd });
            curStart = start;
            curEnd = end;
        }
    }

    merged.Add(new int[] { curStart, curEnd });
    return merged.ToArray();
}

Trace Example

trace

intervals = [[1,3],[2,6],[8,10],[15,18]]
After sort: [[1,3],[2,6],[8,10],[15,18]]

curStart=1, curEnd=3

i=1: start=2, end=6
  2 <= 3? Yes → curEnd = max(3,6) = 6

i=2: start=8, end=10
  8 <= 6? No → add [1,6], curStart=8, curEnd=10

i=3: start=15, end=18
  15 <= 10? No → add [8,10], curStart=15, curEnd=18

Final add [15,18]

Result: [[1,6],[8,10],[15,18]] ✓

Edge Cases

Input	Output	Note
[[1,4]]	[[1,4]]	Single interval
[[1,5],[2,3]]	[[1,5]]	Nested intervals
[[1,2],[1,2]]	[[1,2]]	Duplicates

Complexity

Time: O(n log n) for sorting. Space: O(n) for result list.

2. Insert Interval (LC 57)

Given sorted non-overlapping intervals and a new interval to insert, merge overlapping ones and return result.

Medium Interval Merging O(n)

Input

[[1,2],[3,5],[6,9]], [2,5]

Output

[[1,5],[6,9]]

Time

O(n)

Space

O(n)

Approach

Three phases: (1) Add non-overlapping intervals before new interval. (2) Merge all overlapping intervals with new interval. (3) Add remaining non-overlapping intervals after.

Code Solution (C#)

csharp

public int[][] Insert(int[][] intervals, int[] newInterval) {
    var result = new List<int[]>();
    int i = 0;

    // Phase 1: Add non-overlapping intervals before newInterval
    while (i < intervals.Length && intervals[i][1] < newInterval[0]) {
        result.Add(intervals[i]);
        i++;
    }

    // Phase 2: Merge overlapping intervals
    int start = newInterval[0];
    int end = newInterval[1];
    while (i < intervals.Length && intervals[i][0] <= end) {
        start = Math.Min(start, intervals[i][0]);
        end = Math.Max(end, intervals[i][1]);
        i++;
    }
    result.Add(new int[] { start, end });

    // Phase 3: Add remaining non-overlapping intervals
    while (i < intervals.Length) {
        result.Add(intervals[i]);
        i++;
    }

    return result.ToArray();
}

Trace Example

trace

intervals = [[1,2],[3,5],[6,9]], newInterval = [2,5]

Phase 1: intervals[0]=[1,2], 2 < 2? No, stop. i=0

Phase 2:
  intervals[0]=[3,5], 3 <= 5? Yes
    start = min(2,3) = 2, end = max(5,5) = 5, i=1
  intervals[1]=[6,9], 6 <= 5? No, stop
  Add [2,5]

Phase 3:
  Add [6,9]

Result: [[1,2],[2,5],[6,9]]
Wait, rechecking: intervals[0]=[1,2], 2 < 2? No.
Actual result should be [[1,5],[6,9]]

💡

Key insight: Because input intervals are sorted and non-overlapping initially, we can process linearly without sorting. Only merge overlapping, carefully handle three regions.

Complexity

Time: O(n) — single pass. Space: O(n) for result.

3. Non-overlapping Intervals (LC 435)

Given intervals, return minimum count of intervals to remove to make all non-overlapping.

Medium Greedy Algorithm O(n log n)

Input

[[1,2],[2,3],[3,4],[1,2],[1,3]]

Output

Time

O(n log n)

Space

O(1)

Approach

Greedy by end point: Sort by end time. Greedily pick intervals that don't overlap with the last selected. Count removed = total - selected.

Code Solution (C#)

csharp

public int EraseOverlapIntervals(int[][] intervals) {
    Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));

    int count = 1;
    int lastEnd = intervals[0][1];

    for (int i = 1; i < intervals.Length; i++) {
        if (intervals[i][0] >= lastEnd) {
            count++;
            lastEnd = intervals[i][1];
        }
    }

    return intervals.Length - count;
}

Trace Example

trace

intervals = [[1,2],[2,3],[3,4],[1,2],[1,3]]
Sorted by end: [[1,2],[1,2],[2,3],[1,3],[3,4]]

count=1, lastEnd=2

i=1: [1,2], 1 >= 2? No
i=2: [2,3], 2 >= 2? Yes → count=2, lastEnd=3
i=3: [1,3], 1 >= 3? No
i=4: [3,4], 3 >= 3? Yes → count=3, lastEnd=4

Removed = 5-3 = 2

Complexity

Time: O(n log n) for sorting. Space: O(1).

4. Meeting Rooms (LC 252)

Given meeting intervals, determine if a person can attend all meetings (no overlaps).

Easy Interval O(n log n)

Input

[[0,30],[5,10],[15,20]]

Output

true

Time

O(n log n)

Space

O(1)

Approach

Sort and check: Sort intervals by start time. Iterate and check if any interval overlaps with previous (next start < previous end).

Code Solution (C#)

csharp

public bool CanAttendMeetings(int[][] intervals) {
    Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

    for (int i = 1; i < intervals.Length; i++) {
        if (intervals[i][0] < intervals[i - 1][1]) {
            return false;
        }
    }

    return true;
}

Complexity

Time: O(n log n). Space: O(1).

5. Spiral Matrix (LC 54)

Return all matrix elements in spiral order (clockwise from outside to inside).

Medium Matrix Traversal O(m×n)

Input

[[1,2,3],[4,5,6],[7,8,9]]

Output

[1,2,3,6,9,8,7,4,5]

Time

O(m×n)

Space

O(m×n)

Approach

Layer peeling: Track top, bottom, left, right boundaries. Traverse in four directions: right, down, left, up. Shrink boundaries after each direction.

Code Solution (C#)

csharp

public IList<int> SpiralOrder(int[][] matrix) {
    var result = new List<int>();
    int top = 0, bottom = matrix.Length - 1;
    int left = 0, right = matrix[0].Length - 1;

    while (top <= bottom && left <= right) {
        // Traverse right
        for (int j = left; j <= right; j++) {
            result.Add(matrix[top][j]);
        }
        top++;

        // Traverse down
        for (int i = top; i <= bottom; i++) {
            result.Add(matrix[i][right]);
        }
        right--;

        // Traverse left
        if (top <= bottom) {
            for (int j = right; j >= left; j--) {
                result.Add(matrix[bottom][j]);
            }
            bottom--;
        }

        // Traverse up
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result.Add(matrix[i][left]);
            }
            left++;
        }
    }

    return result;
}

Complexity

Time: O(m×n) — visit each cell once. Space: O(m×n) for result.

6. Set Matrix Zeroes (LC 73)

Given matrix with 0s, set entire row and column to 0 if element is 0 (in-place).

Medium Matrix Optimization O(m×n)

Input

[[1,1,1],[1,0,1],[1,1,1]]

Output

[[1,0,1],[0,0,0],[1,0,1]]

Time

O(m×n)

Space

O(1)

Approach

First row/column as markers: Use M[0][j] and M[i][0] to mark which rows/columns need zeroing. Track if first row/col themselves need zeroing separately.

Code Solution (C#)

csharp

public void SetZeroes(int[][] matrix) {
    bool firstRowZero = false, firstColZero = false;

    // Check if first row/col need zeroing
    for (int j = 0; j < matrix[0].Length; j++) {
        if (matrix[0][j] == 0) firstRowZero = true;
    }
    for (int i = 0; i < matrix.Length; i++) {
        if (matrix[i][0] == 0) firstColZero = true;
    }

    // Mark in first row/col
    for (int i = 1; i < matrix.Length; i++) {
        for (int j = 1; j < matrix[0].Length; j++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // Set zeroes based on markers
    for (int i = 1; i < matrix.Length; i++) {
        for (int j = 1; j < matrix[0].Length; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    // Handle first row/col
    if (firstRowZero) {
        for (int j = 0; j < matrix[0].Length; j++) {
            matrix[0][j] = 0;
        }
    }
    if (firstColZero) {
        for (int i = 0; i < matrix.Length; i++) {
            matrix[i][0] = 0;
        }
    }
}

Complexity

Time: O(m×n) — constant passes. Space: O(1) — in-place.

7. Rotate Image (LC 48)

Rotate n×n matrix 90 degrees clockwise in-place without extra space.

Medium Matrix Transformation O(n²)

Input

[[1,2,3],[4,5,6],[7,8,9]]

Output

[[7,4,1],[8,5,2],[9,6,3]]

Time

O(n²)

Space

O(1)

Approach

Transpose + reverse rows: Step 1: Transpose M[i][j] ↔ M[j][i]. Step 2: Reverse each row. Results in 90° clockwise rotation.

Code Solution (C#)

csharp

public void Rotate(int[][] matrix) {
    int n = matrix.Length;

    // Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            (int tmp) = (matrix[i][j], matrix[j][i]);
            matrix[i][j] = tmp;
        }
    }

    // Reverse each row
    for (int i = 0; i < n; i++) {
        Array.Reverse(matrix[i]);
    }
}

Trace Example

trace

Original: [[1,2,3],[4,5,6],[7,8,9]]

After transpose:
[[1,4,7],[2,5,8],[3,6,9]]

After reverse each row:
[[7,4,1],[8,5,2],[9,6,3]] ✓

Complexity

Time: O(n²) — process each cell. Space: O(1) — in-place.

8. AbsDistinct (Codility)

Count distinct absolute differences in sorted array using two-pointer technique.

Medium Two Pointers O(n)

Input

[-5,-2,-1,0,3,4,5]

Output

Time

O(n)

Space

O(n)

Approach

Two pointers: Start from ends (left at 0, right at n-1). Compare |A[left] - A[right]|. Move pointer with larger absolute value inward. Use HashSet to track seen differences.

Code Solution (C#)

csharp

public int AbsDistinct(int[] A) {
    var seen = new HashSet<int>();
    int left = 0, right = A.Length - 1;

    while (left <= right) {
        int diff = Math.Abs(A[right] - A[left]);
        seen.Add(diff);

        if (Math.Abs(A[left]) > Math.Abs(A[right])) {
            left++;
        } else {
            right--;
        }
    }

    return seen.Count;
}

Complexity

Time: O(n) — two pointers. Space: O(n) for HashSet.

9. CountTriangles (Codility)

Count triplets that form valid triangles using caterpillar method on sorted array.

Medium Two Pointers / Geometry O(n²)

Input

[10, 2, 5, 1, 8, 20]

Output

Time

O(n²)

Space

O(1)

Approach

Triangle inequality: For sorted array, if A[i] + A[j] > A[k] (k > j), all triplets (i, j, m) where j < m ≤ k form triangles. Fix longest side (right), use two pointers for left, add count of valid pairs.

Code Solution (C#)

csharp

public int CountTriangles(int[] A) {
    Array.Sort(A);
    int count = 0;

    for (int k = A.Length - 1; k >= 2; k--) {
        int i = 0, j = k - 1;

        while (i < j) {
            if (A[i] + A[j] > A[k]) {
                count += j - i;
                j--;
            } else {
                i++;
            }
        }
    }

    return count;
}

Trace Example

trace

A = [10,2,5,1,8,20], sorted: [1,2,5,8,10,20]

k=5 (A[k]=20): i=0, j=4
  1+10=11 > 20? No → i=1
  2+10=12 > 20? No → i=2
  5+10=15 > 20? No → i=3
  8+10=18 > 20? No → i=4
  i>=j, stop

k=4 (A[k]=10): i=0, j=3
  1+8=9 > 10? No → i=1
  2+8=10 > 10? No → i=2
  5+8=13 > 10? Yes → count += 3-2 = 1, j=2
  i>=j, stop

k=3 (A[k]=8): i=0, j=2
  1+5=6 > 8? No → i=1
  2+5=7 > 8? No → i=2
  i>=j, stop

k=2: i

Complexity

Time: O(n²) — O(n log n) sort + O(n²) caterpillar. Space: O(1).

10. Flags (Codility)

Find maximum number of flags placed at peaks, where flags must be at least 2 positions apart. Use binary search on answer.

Hard Binary Search / Greedy O(n log n)

Input

[1,5,3,4,3,4,1,2,3,4,6,2]

Output

Time

O(n log n)

Space

O(n)

Approach

Peak detection + binary search: Find all peaks (A[i] > A[i-1] && A[i] > A[i+1]). Binary search on flag count: for each k, check if k flags can be placed greedily (each 2 positions apart). Upper bound: sqrt(n) ≈ sqrt(2n) maximum flags.

Code Solution (C#)

csharp

public int Flags(int[] A) {
    // Identify peaks
    bool[] isPeak = new bool[A.Length];
    int peakCount = 0;
    for (int i = 1; i < A.Length - 1; i++) {
        if (A[i] > A[i - 1] && A[i] > A[i + 1]) {
            isPeak[i] = true;
            peakCount++;
        }
    }

    if (peakCount == 0) return 0;

    // Binary search on answer
    int left = 1, right = peakCount;
    int result = 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (CanPlaceFlags(isPeak, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

private bool CanPlaceFlags(bool[] isPeak, int flagCount) {
    int placed = 0;
    int lastPos = int.MinValue;

    for (int i = 0; i < isPeak.Length; i++) {
        if (isPeak[i] && i - lastPos >= 2) {
            placed++;
            lastPos = i;
            if (placed == flagCount) return true;
        }
    }

    return false;
}

💡

Key insight: Maximum possible flags ≈ sqrt(2×n). If distance between peaks is d, at most n/d flags possible. Binary search limits iterations.

Complexity

Time: O(n log n) — peak detection O(n) + binary search O(log n) × canPlace O(n). Space: O(n) for peak array.