How to find the minimum range

Question

I have a java Map:

 Map<String, ArrayList<Integer>> positions = new HashMap<String, ArrayList<Integer>>();

Basically this map Contains:

 word1: 2 10 17 
 word2: 3  8 15 20
 word3: 6  9 19 22
 word4: 7 12 18 24
 ..... and so on

Now I want to find the minimum range between all the word positions. We will have unique and sorted positions (i.e. no two integers will be same).

The minimum range here is 3 (between 10, 8, 9 and 7)

How should we approach this problem?

I thought of the following steps:

    1) Have pointers as many as words length.
    2) In this example, we have 4 pointers, pointing towards 2, 3, 6 and 7.
    3) The range is calculated which comes out be 5.
    4) Keep this range in a certain variable say 'min'.
    5) Repeat until all positions in all lists have not been read:
        a) Move the lowest pointer to the next in the list(In this example, we move pointer-1 to point to 10).
        b) Calculate the range again (this comes to be 7 now).
        c) If the new range < min:
             min = new range
    6) Return 'min'

But I don't know how to approach this in Java. Can somebody help me out? If you have certain different approach, I would welcome it.

Answer 1

Here's the solution I came up with (was written in C#, but the basic idea should be transferable to Java)

public class RangeFinder
{
    public List<List<int>> WordList { get; set; }
    public List<int> IndexList { get; private set; }

    public int MinRange()
    {
        IndexList = new List<int>();
        for (int i = 0; i < WordList.Count; i++)
        {
            IndexList.Add(0);
        }
        int min = Int32.MaxValue;
        do
        {
            var range = CalculateRange();
            if (range < min)
            {
                min = range;
            }
        }
        while (!EndReached());
        return min;
    }

    private int CalculateRange()
    {
        var maxVal = Int32.MinValue;
        var minVal = Int32.MaxValue;
        for (int i = 0; i < WordList.Count; i++)
        {
            var word = WordList[i];
            var val = word[IndexList[i]];
            if(val > maxVal)
            {
                maxVal = val;
            }
            if(val < minVal)
            {
                minVal = val;
            }
        }
        return maxVal - minVal;
    }

    private bool EndReached()
    {
        for(int i=0; i < IndexList.Count; i++)
        {
            var word = WordList[i];
            var wordCount = word.Count;
            IndexList[i] = (++IndexList[i]) % wordCount;
            if(IndexList[i] > 0)
            {
                return false;
            }
        }
        return true;
    }
}

A brief overview of how it works: The WordList gets populated when the class is created (for Java, create a constructor that populates the WordList). In my test code, I just created a List for each word and made a list of each of those words. The IndexList keeps track of which number we're looking at with each word. They all start at index 0. Then, we increment the first word. When the first word's index wraps, we increment the second word. When the second word's index wraps, we increment the third word. This goes on until the last word's index wraps. When that occurs, we know all possible combinations have been looked at and we can return the min range.