An algorithm that finds the number of "lined up columns"

I found this question in an old exam in computer science. I solved it in a good way, but I'm not convinced that my solution is the best solution. I believe that there's a better way to solve it.


Given N Columns that are lined up, The horizontal distance
between two adjacent columns (The lower edges) is exactly 1 meter. The
columns heights are different, and they can only be positive integers
(In meters). Let's call a Pair of columns (not necessarily adjacent)
"A Good Pair" if the imaginary line that connects their upper edges creates a gradient of 45 degrees relatively with the ground. The
slope can go from Left to Right, or from Right to Left. I have to
write an algorithm that will count all the "Good Pairs" of columns
that exist. Notice that 1 column could participate in more than 1
"Good Pair".


The algorithm must be written in the most efficient way, and have the
best performance (The less Run-Time possible).


It's input:


N, Which represents the number of columns, 5

• Column 2 and column 4

• Column 2 and column 6

• Column 4 and column 5

• Column 4 and column 6

Here's my solution:

static void Main(string[] args)
{
    int n, count = 0; int[] heightList;
    Console.WriteLine("Enter the number of columns");
    n = int.Parse(Console.ReadLine());
    heightList = new int[n];

    Console.WriteLine("Enter the list of heights");
    for (int i = 0; i < heightList.Length; i++)
    {
        heightList[i] = int.Parse(Console.ReadLine());
    }

    for (int i = 0; i < heightList.Length; i++)
    {
        for (int j = i+1; j < heightList.Length; j++)
        {
            //Checking if the pair creates a gradient of 45 degrees with the ground.
            if (Math.Abs(heightList[j] - heightList[i]) == Math.Abs(j - i))
            {
                count++;
            }
        }
    }

    Console.WriteLine(count);
    Console.ReadLine();
}

Is there any better way to solve this question?

You loop over all pairs, which costs O(n^2) time. This is not necessary.

You can partition your input in "good sets": such a set consists of all columns that are on a certain 45-degree line. Every column is in exactly two such sets. You can identify the set by - for instance - its intersection with the x-axis (which is always an integer) plus wether it is upward or downward. As an example, column 3, which has height 5, is in set -2 (upward diagonal) and set 8 (downward diagonal).

Create two hashmaps (one for upward, one for downward) with set identifier as key and number of columns in there as value. You can create these maps in linear time. Now, a set consisting of n columns has n choose 2 = n(n-1)/2 good pairs. Adding them all up gives your answer, still in linear time.

In code, that would be something like:

public static int CountGoodPairs(params int[] heights)
{   
    var upCounts = new Dictionary();
    var downCounts = new Dictionary();

    for (var i = 0; i  c * (c - 1) / 2);
}

private static void IncrementCount(Dictionary counts, int key)
{
    var count = 0;
    counts.TryGetValue(key, out count);
    counts[key] = count+1;
}

StackExchange Code Review Q#78765, answer score: 6