7
\$\begingroup\$

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

enter image description here

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?

\$\endgroup\$
6
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • \$\begingroup\$ Well, I understood your solution a bit, but not that deep. I tested your code in C#, the print wasn't correct. In the example in my question, the print should be 5, while it printed 10. I also tested a different input, it's incorrect too. I couldn't find the mistake.. Thank you. \$\endgroup\$
    – Buk Lau
    Jan 27 '15 at 17:34
  • \$\begingroup\$ Since we are in Code Review: you could use the method signature with params. Example: public static int CountGoodPairs(params int[] heights). \$\endgroup\$ Jan 27 '15 at 17:52
  • \$\begingroup\$ @BukLau You're right, there were 2 small issues. First of all, I forgot to divide by 2 (and thus counted both (1, 3) and (3, 1), for instance). Second, we need a way to distinguish the upward and downward diagonals. I split them into two dictionaries now. \$\endgroup\$ Jan 27 '15 at 18:01
  • \$\begingroup\$ @VincentvanderWeele your solution worked, but I still don't understand the way you solved it. There are many things in your code that I haven't learned yet. I don't know how to use many things in it, such as the Dictionary<int, int>() where I assumed it's an array. And TryGetValue(key, out count); and some others. I don't know what these things are. If there's anyway you can make it more simple for me (using the format of code for my solution) I'd really appreciate it! Thank you. \$\endgroup\$
    – Buk Lau
    Jan 27 '15 at 19:54
  • \$\begingroup\$ @BukLau I'm afraid the dictionary is really necessary. A dictionary with integer key (as in this case) can be seen as a sparse array: a huge array in which only very few indices actually contain data (and where the indices can be negative). This is needed because the column heights can be any value and we don't want to create a huge array for nothing. Since not all indices in the dictionary exist, we need to check an index before using. That's where TryGetValue comes in: after that line count is the value at index key if it exists. Otherwise, it is the default from the line above. \$\endgroup\$ Jan 28 '15 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.