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

Question

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 < N < 500,000 followed by a list of N positive integers that represent the heights of the columns, as the 1st number in the list is the 1st column's height and the 2nd is for the 2nd column, and so on. The algorithm has to print the number of "Good Pairs" that exist in the list.

Example:

N = 6, and the list of numbers: 3, 5, 5, 3, 4, 1. (The most left number represents the 1st columns height).

The algorithm should print 5 because there are 5

"Good Pairs":

• Column 1 and column 3
• 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?

Answer 1

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<int, int>();
    var downCounts = new Dictionary<int, int>();

    for (var i = 0; i < heights.Length; i++)
    {
        var height = heights[i];    
        IncrementCount(upCounts, i - height);
        IncrementCount(downCounts, i + height);
    }

    return upCounts.Values
                   .Concat(downCounts.Values)
                   .Sum(c => c * (c - 1) / 2);
}

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