Dijkstra's Variation

Usually Dijkstra's Algorithm is used to find weighted {min, max} paths in a graph. It does have a well-structured format. Sometimes, though, a slight variation is needed. Here is a problem to exemplify it: https://leetcode.com/problems/path-with-maximum-minimum-value/

1102. Path With Maximum Minimum Value
Medium
Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0,0] and ending at [R-1,C-1].
The score of a path is the minimum value in that path.  For example, the value of the path 8 →  4 →  5 →  9 is 4.
path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).

Example 1:
Input: [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: 
The path with the maximum score is highlighted in yellow. 
Example 2:
Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2
Example 3:
Input: [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
Output: 3

Note:
  1. 1 <= R, C <= 100
  2. 0 <= A[i][j] <= 10^9

Usually the structure for Dijkstra's Algorithm is this:

Use a priority queue
Enqueue
While queue is not empty
      Dequeue
      Check whether you have reached your target
      Mark as visited
      For all neighbors
          Enqueue neighbor

The traditional Dijkstra's Algorithm only marks as visited during the processing, and it also allows elements to be enqueued multiple times. It still has a polynomial time complexity.
But in the problem above the variation that I'm referring to will exactly "break" these two rules. First, the visiting flag will happen whenever we enqueue. Second, we won't allow the same element to be enqueued twice. This is because the problem is very close to a non-weighted straight BFS, with the caveat that we should always lean towards the max elements in the path (hence the use of a priority queue). Works well. Code is below, cheers, ACC.


public class Solution
{
    public int MaximumMinimumPath(int[][] A)
    {
        PriorityQueue pQueue = new PriorityQueue();
        Hashtable visited = new Hashtable();

        QueueItem qi = new QueueItem(0, 0, A[0][0]);
        pQueue.Enqueue(qi, A[0][0]);
        visited.Add(qi.key, true);

        while (pQueue.Count > 0)
        {
            QueueItem current = (QueueItem)pQueue.Dequeue();

            if (current.row == A.Length && current.col == A[A.Length - 1].Length) return current.minVal;

            int[] rowDelta = { 1, -1, 0, 0 };
            int[] colDelta = { 0, 0, 1, -1 };

            for (int i = 0; i < rowDelta.Length; i++)
            {
                int nRow = current.row + rowDelta[i];
                int nCol = current.col + colDelta[i];

                if (nRow >= 0 &&
                    nRow < A.Length &&
                    nCol >= 0 &&
                    nCol < A[nRow].Length)
                {
                    QueueItem nqi = new QueueItem(nRow, nCol, Math.Min(current.minVal, A[nRow][nCol]));
                    if (!visited.ContainsKey(nqi.key))
                    {
                        pQueue.Enqueue(nqi, A[nRow][nCol]);
                        visited.Add(nqi.key, true);
                    }
                }
            }
        }

        return -1;
    }
}

public class QueueItem
{
    public int row = 0;
    public int col = 0;
    public int minVal = 0;
    public int key = 0;

    public QueueItem(int row, int col, int minVal)
    {
        this.row = row;
        this.col = col;
        this.minVal = minVal;
        this.key = 200 * row + col;
    }
}
public class PriorityQueue
{
    public struct HeapEntry
    {
        private object item;
        private int priority;
        public HeapEntry(object item, int priority)
        {
            this.item = item;
            this.priority = priority;
        }
        public object Item
        {
            get
            {
                return item;
            }
        }
        public BigInteger Priority
        {
            get
            {
                return priority;
            }
        }
    }

    private int count;
    private int capacity;
    private HeapEntry[] heap;

    public int Count
    {
        get
        {
            return this.count;
        }
    }

    public PriorityQueue()
    {
        capacity = 100000;
        heap = new HeapEntry[capacity];
    }

    public object Dequeue(/*ref long weight*/)
    {
        object result = heap[0].Item;
        //weight = heap[0].Priority;
        count--;
        trickleDown(0, heap[count]);
        return result;
    }

    public void Enqueue(object item, int priority)
    {
        count++;
        bubbleUp(count - 1, new HeapEntry(item, priority));
    }

    private void bubbleUp(int index, HeapEntry he)
    {
        int parent = (index - 1) / 2;
        // note: (index > 0) means there is a parent
        while ((index > 0) && (heap[parent].Priority < he.Priority))
        {
            heap[index] = heap[parent];
            index = parent;
            parent = (index - 1) / 2;
        }
        heap[index] = he;
    }

    private void trickleDown(int index, HeapEntry he)
    {
        int child = (index * 2) + 1;
        while (child < count)
        {
            if (((child + 1) < count) &&
                (heap[child].Priority < heap[child + 1].Priority))
            {
                child++;
            }
            heap[index] = heap[child];
            index = child;
            child = (index * 2) + 1;
        }
        bubbleUp(index, he);
    }
}

Comments

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons