What is wrong with my IEquatable<T>, IComparable<T> implementation? SortedList throws ArgumentException

Question

I am working on solving a puzzle online and stumbled upon this problem where given a 2D matrix and a number k, I need to return the kth smallest element in the matrix.

 matrix = [
       [ 1,  5,  9],
       [10, 11, 13],
       [12, 13, 15]
    ],
    k = 8,

return 13.

I am able to solve this problem with my own implementation of a Binary Heap. Since I am preparing for interviews, I am not sure if implementing my own Heap is an acceptable solution in all cases. So I tried to solve this with SortedList/SortedSet.

I am basically creating a Point object that takes index i, j and the value at i, j. I have implemented IComparable and IEquatable. But for some reason, with the above example, the Point object for index 1,2(value 13) and the one for index 2,1(value 13) are being considered equal when they shouldn't be. I get an ArgumentException when using a SortedList, a SortedSet meanwhile just overwrites the existing object. Is my implementation of IEquatable, IComparable wrong? I have double checked that they generate different hashcodes.

P.S. This is not a homework problem. I am solving questions from an online interview prep platform.

public class Solution {
    public int KthSmallest(int[,] matrix, int k) {
        int rows = matrix.GetLength(0);
        int cols = matrix.GetLength(1);
        SortedSet<Point> pq = new SortedSet<Point>();
        bool[,] visited = new bool[rows, cols];
        int count = 1;
        int i=0, j=0;
        var start = new Point(i, j, matrix[i, j]);
        pq.Add(start);
        visited[0, 0] = true;
        while(true) {
            k--;
            var curr = pq.Min;
            pq.Remove(pq.First());
            if(k == 0)
                return curr.val;
            i = curr.x + 1;
            j = curr.y;
            if(i < rows && j < cols && !visited[i, j]) {
                var next = new Point(i, j, matrix[i, j]);
                Console.WriteLine(next.GetHashCode());
                Console.WriteLine(i+", "+j+", "+next.val);
                pq.Add(next);
                visited[i, j] = true;
            }
            i = curr.x;
            j = curr.y + 1;
            if(i < rows && j < cols && !visited[i, j]) {
                var next = new Point(i, j, matrix[i, j]);
                Console.WriteLine(next.GetHashCode());
                Console.WriteLine(i+", "+j+", "+next.val);
                pq.Add(next);
                visited[i, j] = true;
            }
        }
    }
}


public class Point : IComparable<Point>, IEquatable<Point>
{
    public int x { get; private set; }
    public int y { get; private set; }
    public int val { get; private set; }

    public Point(int x, int y, int val)
    {
        this.x = x;
        this.y = y;
        this.val = val;
    }

    public int CompareTo(Point that)
    {
        if(this.val == that.val) {
            if(this.x == that.x) {
                return this.y.CompareTo(that.y);
            }
            else {
                this.x.CompareTo(that.x);
            }
        }
        return val.CompareTo(that.val);
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((Point)obj);
    }

    public bool Equals(Point p1) {
        return x == p1.x && y == p1.y && val == p1.val;
    }

    public override int GetHashCode() {
        long hashCode = ((x * 31 + y) * 31 + val);
        return hashCode.GetHashCode();
    }
}

Answer 1

You're missing a return statement in your CompareTo. I commented your original below, along with a corrected version. In the case of comparing [2,1] and [1,2], the x values don't match, but when you hit the this.x.CompareTo, you never actually return that comparison, so instead your value comparison returns.

You have:

public int CompareTo(Point that)
    {
        if(this.val == that.val) {
            if(this.x == that.x) {
                return this.y.CompareTo(that.y);
            }
            else {
                //****MISSING RETURN STATEMENT - 
                //will return the val.ComapreTo statement after 
                //it leaves this block*****
                this.x.CompareTo(that.x);
            }
        }
        return val.CompareTo(that.val);
    }

You need:

public int CompareTo(Point that)
    {
        if(this.val == that.val) {
            if(this.x == that.x) {
                return this.y.CompareTo(that.y);
            }
            else {
                return this.x.CompareTo(that.x);
            }
        }
        return val.CompareTo(that.val);
    }