LeetCode 986 - Interval List Intersections

https://leetcode.com/problems/interval-list-intersections/

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:

1. 0 <= A.length < 1000
2. 0 <= B.length < 1000
3. 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

https://leetcode.com/articles/interval-list-intersections/
https://leetcode.com/problems/interval-list-intersections/discuss/231122/Java-two-pointer-O(m-%2B-n)

In an interval [a, b], call b the "endpoint".

Among the given intervals, consider the interval A[0] with the smallest endpoint. (Without loss of generality, this interval occurs in array A.)

Then, among the intervals in array B, A[0] can only intersect one such interval in array B. (If two intervals in B intersect A[0], then they both share the endpoint of A[0] -- but intervals in B are disjoint, which is a contradiction.)

Algorithm

If A[0] has the smallest endpoint, it can only intersect B[0]. After, we can discard A[0] since it cannot intersect anything else.

Similarly, if B[0] has the smallest endpoint, it can only intersect A[0], and we can discard B[0] after since it cannot intersect anything else.

We use two pointers, i and j, to virtually manage "discarding" A[0] or B[0] repeatedly.

  public Interval[] intervalIntersection(Interval[] A, Interval[] B) {

    List<Interval> ans = new ArrayList<>();

    int i = 0, j = 0;

    while (i < A.length && j < B.length) {

      // Let's check if A[i] intersects B[j].

      // lo - the startpoint of the intersection

      // hi - the endpoint of the intersection

      int lo = Math.max(A[i].start, B[j].start);

      int hi = Math.min(A[i].end, B[j].end);

      if (lo <= hi)

        ans.add(new Interval(lo, hi));

      // Remove the interval with the smallest endpoint

      if (A[i].end < B[j].end)

        i++;

      else

        j++;

    }

    return ans.toArray(new Interval[ans.size()]);

  }

X.
https://leetcode.com/problems/interval-list-intersections/discuss/231108/C%2B%2B-O(n)-%22merge-sort%22

public Interval[] intervalIntersection(Interval[] A, Interval[] B) {
    List<Interval> list = new ArrayList<>();
    for(int i=0, j=0; i < A.length && j < B.length; ) {
        if(A[i].end < B[j].start) i++;
        else if(B[j].end < A[i].start) j++;
        else {
            int start = Math.max(A[i].start, B[j].start);
            int end = Math.min(A[i].end, B[j].end);
            list.add(new Interval(start, end));
            
            if(A[i].end < B[j].end) i++;
            else j++;
        }
    }
    return list.toArray(new Interval[list.size()]);
}

LeetCode 766 - Toeplitz Matrix

https://leetcode.com/problems/toeplitz-matrix/description/

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: True
Explanation:
1234
5123
9512

In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.

Example 2:

Input: matrix = [[1,2],[2,2]]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.

Note:

1. matrix will be a 2D array of integers.
2. matrix will have a number of rows and columns in range [1, 20].
3. matrix[i][j] will be integers in range [0, 99].

https://leetcode.com/problems/toeplitz-matrix/solution/
Approach #2: Compare With Top-Left Neighbor [Accepted]

For each diagonal with elements in order $a_1, a_2, a_3, \dots, a_k$, we can check $a_1 = a_2, a_2 = a_3, \dots, a_{k-1} = a_k$. The matrix is Toeplitz if and only if all of these conditions are true for all (top-left to bottom-right) diagonals.

Every element belongs to some diagonal, and it's previous element (if it exists) is it's top-left neighbor. Thus, for the square (r, c), we only need to check r == 0 OR c == 0 OR matrix[r-1][c-1] == matrix[r][c].

For each diagonal with elements in order a1,a2,a3,…,ak$a_1,a_2,a_3,\dots ,a_k$, we can check a1=a2,a2=a3,…,ak−1=ak$a_1=a_2,a_2=a_3,\dots ,a_{k-1}=a_k$. The matrix is Toeplitz if and only if all of these conditions are true for all (top-left to bottom-right) diagonals.

Every element belongs to some diagonal, and it's previous element (if it exists) is it's top-left neighbor. Thus, for the square (r, c), we only need to check r == 0 OR c == 0 OR matrix[r-1][c-1] == matrix[r][c].

    public boolean isToeplitzMatrix(int[][] matrix) {
        for (int r = 0; r < matrix.length; ++r)
            for (int c = 0; c < matrix[0].length; ++c)
                if (r > 0 && c > 0 && matrix[r-1][c-1] != matrix[r][c])
                    return false;
        return true;
    }
https://leetcode.com/problems/toeplitz-matrix/discuss/113422/C%2B%2BJava-Clean-Code

    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (matrix[i][j] != matrix[i - 1][j - 1])
                    return false;
        return true;
    }




public boolean isToeplitzMatrix(int[][] matrix) {

  int row = matrix.length;

  int col = matrix[0].length;

  for (int i = 0; i < row; i++) {

    int ti = i;

    int val = matrix[ti][0];

    for (int j = 0; j < col && ti < row; j++) {

      if (matrix[ti][j] != val)

        return false;

      ti++;

    }

  }

  for (int j = 0; j < col; j++) {

    int tj = j;

    int val = matrix[0][tj];

    for (int i = 0; i < row && tj < col; i++) {

      if (matrix[i][tj] != val)

        return false;

      tj++;

    }

  }

  return true;

}

Approach #1: Group by Category

Intuition and Algorithm

We ask what feature makes two coordinates (r1, c1) and (r2, c2) belong to the same diagonal?

It turns out two coordinates are on the same diagonal if and only if r1 - c1 == r2 - c2.

This leads to the following idea: remember the value of that diagonal as groups[r-c]. If we see a mismatch, the matrix is not Toeplitz; otherwise it is.

  public boolean isToeplitzMatrix(int[][] matrix) {

    Map<Integer, Integer> groups = new HashMap();

    for (int r = 0; r < matrix.length; ++r) {

      for (int c = 0; c < matrix[0].length; ++c) {

        if (!groups.containsKey(r - c))

          groups.put(r - c, matrix[r][c]);

        else if (groups.get(r - c) != matrix[r][c])

          return false;

      }

    }

    return true;

  }

5. Verify if a given matrix is a Toeplitz matrix:
   Follow up, assume that the whole matrix cannot be fit in memory and should be read from a file, assume that a few rows and all columns can be read in, how to verify?

https://leetcode.com/problems/toeplitz-matrix/discuss/147808/Java-Answers-to-the-follow-ups-(load-partial-rowcolumn-one-time)-the-3rd-one-beats-98

the follow-ups (load partial row/column one time)

https://leetcode.com/problems/toeplitz-matrix/discuss/179882/Follow-up-questions
No online judge for the follow-up questions so let's discuss:

1. What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
Compare half of 1 row with half of the next/previous row.
2. What if the matrix is so large that you can only load up a partial row into the memory at once?
Hash 2 rows (so only 1 element needs to be loaded at a time) and compare the results, excluding the appropriate beginning or ending element.