[LeetCode] Total Cost to Hire K Workers

Problem: You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker.

You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:

• You will run k sessions and hire exactly one worker in each session.
• In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
• For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,1,2].
• In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,2,7,7,2]. Please note that the indexing may be changed in the process.
• If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
• A worker can only be chosen once.

Return the total cost to hire exactly k workers.

Example:

Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
Output: 11
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [17,12,10,2,7,2,11,20,8]. The lowest cost is 2, and we break the tie by the smallest index, which is 3. The total cost = 0 + 2 = 2.
- In the second hiring round we choose the worker from [17,12,10,7,2,11,20,8]. The lowest cost is 2 (index 4). The total cost = 2 + 2 = 4.
- In the third hiring round we choose the worker from [17,12,10,7,11,20,8]. The lowest cost is 7 (index 3). The total cost = 4 + 7 = 11. Notice that the worker with index 3 was common in the first and last four workers.
The total hiring cost is 11.

Input: costs = [1,2,4,1], k = 3, candidates = 3
Output: 4
Explanation: We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from [1,2,4,1]. The lowest cost is 1, and we break the tie by the smallest index, which is 0. The total cost = 0 + 1 = 1. Notice that workers with index 1 and 2 are common in the first and last 3 workers.
- In the second hiring round we choose the worker from [2,4,1]. The lowest cost is 1 (index 2). The total cost = 1 + 1 = 2.
- In the third hiring round there are less than three candidates. We choose the worker from the remaining workers [2,4]. The lowest cost is 2 (index 0). The total cost = 2 + 2 = 4.
The total hiring cost is 4.

Constraints:

• 1 <= costs.length <= 105 
• 1 <= costs[i] <= 105
• 1 <= k, candidates <= costs.length

Approach: We can use two heaps / prioriy queues here. One to read from front and one to read from back. If front heap has an element at the top which less than or equal to back heap then we will pop from front heap add the cost in the final cost. We will add the next cost from the front into the front heap. 

If back heap has smaller element than front heap then we will pop from back heap, add it to final cost and then we will add next element from the back to the back heap.

We need to repeat it for k times. We also need to take care that we won't add same elements to both heaps. You can see that in the impelementation. Basicall whenever the nextfront index is greater than nextback index, that means all the elements are already added and we don't need to add the elements again.

That's all!

Implementation in C#:

    public long TotalCost(int[] costs, int k, int candidates)

    {

        int length = costs?.Length ?? 0;

        if (length < k)

        {

            return -1;

        }

        var frontPQ = new PriorityQueue<int, int>();

        var backPQ = new PriorityQueue<int, int>();

        int frontIndex = Math.Min(length, candidates);

        for (int i = 0; i < frontIndex; ++i)

        {

            frontPQ.Enqueue(costs[i], costs[i]);

        }

        int backIndex = Math.Max(frontIndex, length - candidates);

        for (int i = length - 1; i >= backIndex; --i)

        {

            backPQ.Enqueue(costs[i], costs[i]);

        }

        --backIndex;

        long finalCost = 0;

        for (int i = 0; i < k; ++i)

        {

            if (backPQ.Count == 0 ||

                (frontPQ.Count > 0 && frontPQ.Peek() <= backPQ.Peek()))

            {

                int currCost = frontPQ.Dequeue();

                finalCost += currCost;

                if (frontIndex <= backIndex && frontIndex < length)

                {

                    frontPQ.Enqueue(costs[frontIndex], costs[frontIndex]);

                    ++frontIndex;

                }

            }

            else

            {

                int currCost = backPQ.Dequeue();

                finalCost += currCost;

                if (frontIndex <= backIndex && backIndex >= 0)

                {

                    backPQ.Enqueue(costs[backIndex], costs[backIndex]);

                    --backIndex;

                }

            }

        }

        return finalCost;

    }

Complexity: O(candidates + k * log(candidates))

[LeetCode] Maximum Subsequence Score

Problem: You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. You must choose a subsequence of indices from nums1 of length k.

For chosen indices i0, i1, ..., ik - 1, your score is defined as:

• The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.
• It can defined simply as: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).

Return the maximum possible score.

A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} by deleting some or no elements.

Example:

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation: 
The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6. 
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12. 
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.

Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
Output: 30
Explanation: 
Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

Constraints:

• n == nums1.length == nums2.length
• 1 <= n <= 105
• 0 <= nums1[i], nums2[j] <= 105
• 1 <= k <= n

Apporach: The intuition here is to select the k indices that would result in the largest possible sum from nums1 while also ensuring that the minimum value selected from nums2 is as high as possible, because it multiplies the entire sum and we also need to take care these indices might not be coniguous.

How we can do that? If we sort the nums2 array in descending order then we know that maximum possible minimum value is if we include nums2[0.....k] is going to be nums2[k] in the sorted nums2. Now that we have identified how to get the min value from nums2. We need to figure out how to get the sum of those elements from the nums1 which corresponds to the same indices which we are using in nums2 to get the min value.

That means we can't independently sort nums2. What we can do is we can make pair(num1[i], nums2[i]) and sort these list of pairs in the desending order of nums2[i].

Now things become simple for us. We iterate through the list of pairs we created. Given we need to increase the sum as much as possible. We can maintain a heap/priority queue to store k elements of nums1 from the sorted pairs. We keep adding these values as current_sum. When we get more than k elements, we simply calculate current_score as current_sum * pair(nums2[i]) as we know that the current value of nums2 in current pair will be minimum given it is sorted in descending order. Now we can remove the smallest element from the heap safely as we want to get the maximum sum right.

In the end we can retrun the maximum of all the scores we calculated.

That's all!

Implementation in C#:

    public long MaxScore(int[] nums1, int[] nums2, int k)

    {

        int length = nums1?.Length ?? 0;

        if (length < k)

        {

            return -1;

        }

        var pairs = this.CreateSortedPairs(nums1, nums2);

        var pq = new PriorityQueue<int, int>();

        long currSum = 0, maxScore = 0;

        for (int i = 0; i < length; ++i)

        {

            currSum += pairs[i][0];

            pq.Enqueue(pairs[i][0], pairs[i][0]);

            if (pq.Count == k)

            {

                long currScore = currSum * pairs[i][1];

                maxScore = Math.Max(maxScore, currScore);

                currSum -= pq.Dequeue();

            }

        }

        return maxScore;

    }

    private int[][] CreateSortedPairs(int[] nums1, int[] nums2)

    {

        int length = nums1.Length;

        var pairs = new int[length][];

        for (int i = 0; i < length; ++i)

        {

            pairs[i] = new int[2];

            pairs[i][0] = nums1[i];

            pairs[i][1] = nums2[i];

        }

        Array.Sort(pairs, (p1, p2) => {

            return p2[1].CompareTo(p1[1]);

        });

        return pairs;

    }

Complexity: O(nlogn) + O(nlogk)

[LeetCode] Smallest Number in Infinite Set

Problem: You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].

Implement the SmallestInfiniteSet class:

• SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.
• int popSmallest() Removes and returns the smallest integer contained in the infinite set.
• void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.

Example:

Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2);    // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1);    // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
                                   // is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.

Constraints:

• 1 <= num <= 1000
• At most 1000 calls will be made in total to popSmallest and addBack.

Apporach: We can solve this problem using priority queue as we need a data structure which stores the input integers in sorted order given we always have to return smallest number.

The only problem here is how to avoid duplicates as we can have multiple addBack calls for the same number and we don't want to add the same number multiple times. To avoid this situation I am using a HashSet to track the added numbers.

Rest of the solution is straight forward. You can understand it by just looking at the implementation.

Implementation in C#:

public class UniquePriorityQueue

{

    public UniquePriorityQueue()

    {

        this.pq = new PriorityQueue<int, int>();

        this.uniqueSet = new HashSet<int>();

    }

   

    public void Enqueue(int num)

    {

        if (!this.uniqueSet.Contains(num))

        {

            this.pq.Enqueue(num, num);

            this.uniqueSet.Add(num);

        }

    }

    public int Dequeue()

    {

        int num = this.pq.Dequeue();

        this.uniqueSet.Remove(num);

        return num;

    }

    public int Count { get => this.pq.Count; private set{}}

    private PriorityQueue<int, int> pq;

    private HashSet<int> uniqueSet;

}

public class SmallestInfiniteSet

{

    public SmallestInfiniteSet()

    {

        this.pq = new UniquePriorityQueue();

        this.minValue = 1;

        this.maxValue = 1000;

    }

   

    public int PopSmallest()

    {

        if (this.pq.Count > 0)

        {

            return this.pq.Dequeue();

        }

        return this.minValue++;

    }

   

    public void AddBack(int num)

    {

        if (num < this.minValue)

        {

            this.pq.Enqueue(num);

        }

    }

    private UniquePriorityQueue pq;

    private int minValue;

    private int maxValue;

}

Complexity: popSmallest: O(logn), addBack: O(logn)

[LeetCode] Nearest Exit from Entrance in Maze

Problem: You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

Example:

Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Output: 1
Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.

Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
Output: 2
Explanation: There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.

Input: maze = [[".","+"]], entrance = [0,0]
Output: -1
Explanation: There are no exits in this maze.

Approach: This is clearly a Graph BFS problem where a cell is connected to another cell if the other cell is one of top, bottom, left or right cell of the current cell. We just need to find the shortest path from the given cell 'entrance' to any empty cell (contains '.') on the boundary. To get this path we can use BFS as there is same weight here on every edge.

That's all!

Implementation in C#:

    public int NearestExit(char[][] maze, int[] entrance)

    {

        int rows = maze?.Length ?? 0;

        if (rows == 0)

        {

            return -1;

        }

        int cols = maze[0].Length;

        var queue = new Queue<int[]>();

        maze[entrance[0]][entrance[1]] = '+';

        this.AddValidNeighboursToQueue(maze, queue, entrance[0], entrance[1]);

        int steps = 1;

        while (queue.Count > 0)

        {

            int size = queue.Count;

            for (int i = 0; i < size; ++i)

            {

                var cell = queue.Dequeue();

                if (this.IsBoundaryCell(cell, rows, cols))

                {

                    return steps;

                }

                this.AddValidNeighboursToQueue(maze, queue, cell[0], cell[1]);

            }

            ++steps;

        }

        return -1;

    }

    private bool IsBoundaryCell(int[] cell, int rows, int cols)

    {

        return cell[0] == 0 ||

               cell[0] == rows - 1 ||

               cell[1] == 0 ||

               cell[1] == cols - 1;

    }

    private void AddValidNeighboursToQueue(char[][] maze,

                                           Queue<int[]> queue,

                                           int row,

                                           int col)

    {

        // Left neighbour

        if (this.IsValidAndEmptyCell(maze, row, col - 1))

        {

            maze[row][col - 1] = '+';

            queue.Enqueue(new int[] {row, col - 1});

        }

        // Right neighbour

        if (this.IsValidAndEmptyCell(maze, row, col + 1))

        {

            maze[row][col + 1] = '+';

            queue.Enqueue(new int[] {row, col + 1});

        }

        // Top neighbour

        if (this.IsValidAndEmptyCell(maze, row - 1, col))

        {

            maze[row - 1][col] = '+';

            queue.Enqueue(new int[] {row - 1, col});

        }

        // Bottom neighbour

        if (this.IsValidAndEmptyCell(maze, row + 1, col))

        {

            maze[row + 1][col] = '+';

            queue.Enqueue(new int[] {row + 1, col});

        }

    }

    private bool IsValidAndEmptyCell(char[][] maze, int row, int col)

    {

        return row >= 0 &&

               row < maze.Length &&

               col >= 0 &&

               col < maze[0].Length &&

               maze[row][col] == '.';

    }

Complexity: O(n)

[LeetCode] Reorder Routes to Make All Paths Lead to the City Zero

Problem: There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It's guaranteed that each city can reach city 0 after reorder.

Example:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

Constraints:

• 2 <= n <= 5 * 104
• connections.length == n - 1
• connections[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi

Approach: This is clearly a graph as it is already mentioned in the question. Now the intuition is simple all the outgoing edges from 0 must be reversed so that there is a path to reach 0 from every city because it is given that there is only one path between two cities.

Now once the edges from 0 is reversed. We need to do the same for cities directly connected to 0 as there must be incoming path to every city x which is directly connected to 0 from every city directly connected to x, Right? See from example:

0 -> x -> y. We have reversed the path from 0 to x so now graph looks like 0 <- x -> y. How somebody will reach from city y to 0? We need to reverse the path x -> y so that the way now is 0 <- x <- y.

We will keep doing it recursively. With this intuition we can solve this problem using DFS but there are still some problems. Let's see it by example -

0 <- x -> y. As per our graph, there is no outgoing edge from 0 to x so we won't do anything and will return count as 0 as there is no neighbour of 0 given it's directed graph but we can see we have to reverse x -> y path. That means we must have incoming edges too in our graph.

Now the problem is if we store incoming edges how we will come to know if it is incoming edge and I should not reverse it? We can store the original edges in a set and compare before incresasing the count of edges to reverse but what I am doing it in my implementation is that I am pushing negative of city value to identify it given the cities are in range from 0 to n - 1.

Another problem is in case of outgoing edge to node's parent.We should not increase the count in case the connected city or neighbour city is it's parent, right. Consider this example:

0 -> 1 <- 2

Here we will have an positive edge from 2 -> 1 and as per our logice we will increase the count but it should not be the case. To avoid it we just need to check if the edge is ougoing to it's parent itself. Please note that this is happening because we are pushing incoming edges too in our graph.  

Hopefully it's clear now. 

Implementation in C#:

    public int MinReorder(int n, int[][] connections)

    {

        if (n <= 1)

        {

            return 0;

        }

        var cityGraph = this.GenerateCityGraph(connections);

        HashSet<int> visited = new HashSet<int>();

        return this.MinReorderDFS(cityGraph, 0, -1, visited);

    }

    private int MinReorderDFS(Dictionary<int, List<int>> cityGraph,

                              int currCity,

                              int parentCity,

                              HashSet<int> visited)

    {

        if (visited.Contains(currCity))

        {

            return 0;

        }

        visited.Add(currCity);

        int count = 0;

        if (cityGraph.ContainsKey(currCity))

        {

            foreach (int city in cityGraph[currCity])

            {

                if (city > 0 && city != parentCity)

                {

                    ++count;

                }

                count += this.MinReorderDFS(cityGraph,

                                            Math.Abs(city),

                                            currCity,

                                            visited);

            }

        }

        return count;

    }

    private Dictionary<int, List<int>> GenerateCityGraph(int[][] connections)

    {

        var cityGraph = new Dictionary<int, List<int>>();

        foreach (var connection in connections)

        {

            if (!cityGraph.ContainsKey(connection[0]))

            {

                cityGraph[connection[0]] = new List<int>();

            }

            cityGraph[connection[0]].Add(connection[1]);

            if (!cityGraph.ContainsKey(connection[1]))

            {

                cityGraph[connection[1]] = new List<int>();

            }

            cityGraph[connection[1]].Add(-connection[0]);

        }

        return cityGraph;

    }

Complexity: O(n)

[LeetCode] Number of Provinces

Problem: There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Approach: Its kind of finding connected components in a graph problem. We will simply count the number of times we need to do a DFS until all the nodes are visited.

Implementation in C#:

    public int FindCircleNum(int[][] isConnected)

    {

        int rows = isConnected?.Length ?? 0;

        if (rows == 0)

        {

            return 0;

        }

        int cols = isConnected[0].Length;

        HashSet<int> visited = new HashSet<int>();

        int numOfProvinces = 0;

        for (int node = 0; node < rows; ++node)

        {

            if (!visited.Contains(node))

            {

                this.FindCircleNumDFS(node, isConnected, visited);

                ++numOfProvinces;

            }

        }

        return numOfProvinces;

    }

    private void FindCircleNumDFS(int node,

                                  int[][] isConnected,

                                  HashSet<int> visited)

    {

        if (visited.Contains(node))

        {

            return;

        }

        visited.Add(node);

        for (int i = 0; i < isConnected[0].Length; ++i)

        {

            if (isConnected[node][i] == 1)

            {

                this.FindCircleNumDFS(i, isConnected, visited);

            }

        }

    }

Complexity: O(n^2)