3385. Minimum Time to Break Locks II 🔒

Problem Description

Bob needs to escape from a dungeon by breaking n locks in sequence. Each lock requires a certain amount of energy to break, given in an array strength where strength[i] represents the energy needed to break the i-th lock.

Bob uses a sword with special properties to break these locks:

Initial State: The sword starts with 0 energy and a factor X = 1
Energy Growth: Every minute that passes, the sword's energy increases by the current factor X
Breaking Locks: To break the i-th lock, the sword must accumulate at least strength[i] energy
Reset Mechanism: After successfully breaking a lock:
- The sword's energy resets back to 0
- The factor X increases by 1 (so it becomes 2 for the second lock, 3 for the third, and so on)

The goal is to find the minimum total time (in minutes) needed for Bob to break all n locks and escape.

For example, if there are 3 locks with strengths [3, 4, 1]:

For the 1st lock (strength 3): With X = 1, the sword gains 1 energy per minute, taking 3 minutes to reach strength 3
For the 2nd lock (strength 4): With X = 2, the sword gains 2 energy per minute, taking 2 minutes to reach strength 4
For the 3rd lock (strength 1): With X = 3, the sword gains 3 energy per minute, taking 1 minute to reach strength 1
Total time: 3 + 2 + 1 = 6 minutes

The key insight is that Bob can choose the order in which to break the locks, and different orders will result in different total times. The algorithm needs to find the optimal order that minimizes the total time.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: While the problem doesn't explicitly mention a graph, we can model it as a bipartite graph matching problem. We have n locks and n time slots (positions in the breaking sequence), and we need to find the optimal assignment of locks to positions.

Is it a tree?

No: The problem structure is not a tree. It's more of a complete bipartite graph where any lock can be assigned to any position.

Is the problem related to directed acyclic graphs?

No: The problem is not about DAGs or dependencies between locks.

Is the problem related to shortest paths?

No: We're not finding paths through a graph in the traditional sense.

Does the problem involve connectivity?

No: We're not checking if components are connected.

Does the problem have small constraints?

Yes: With n locks, we have n! possible orderings to consider. The constraints are typically small enough to allow exploring different permutations.

DFS/backtracking?

Yes: We can use DFS with backtracking to explore all possible permutations of lock breaking orders and find the minimum time.

Conclusion: The flowchart suggests using DFS/backtracking to solve this problem. We can use DFS to:

Try each unvisited lock at the current position
Calculate the time needed (based on the lock's strength and current factor X)
Recursively solve for the remaining locks
Backtrack and try different orderings
Track the minimum total time across all valid permutations

The solution provided actually uses a more sophisticated approach (Minimum Cost Flow), but the fundamental insight of needing to explore different orderings aligns with the DFS/backtracking pattern identified by the flowchart.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is recognizing that this is fundamentally an assignment problem. We have n locks and n positions in a sequence, and we need to find the optimal assignment that minimizes total time.

Let's think about what happens when we break locks in a certain order:

When breaking the 1st lock (any lock we choose), we have factor X = 1, so time = ⌈strength/1⌉
When breaking the 2nd lock, we have factor X = 2, so time = ⌈strength/2⌉
When breaking the 3rd lock, we have factor X = 3, so time = ⌈strength/3⌉
And so on...

This reveals an important pattern: stronger locks should be broken later when the factor X is higher, because dividing by a larger number reduces the time more significantly. Conversely, weaker locks should be broken early when the factor is small.

However, it's not as simple as just sorting the locks. Consider locks with strengths [10, 9, 8]:

If we break them in order [8, 9, 10]: times are ⌈8/1⌉ + ⌈9/2⌉ + ⌈10/3⌉ = 8 + 5 + 4 = 17
If we break them in order [9, 8, 10]: times are ⌈9/1⌉ + ⌈8/2⌉ + ⌈10/3⌉ = 9 + 4 + 4 = 17
If we break them in order [10, 8, 9]: times are ⌈10/1⌉ + ⌈8/2⌉ + ⌈9/3⌉ = 10 + 4 + 3 = 17

Multiple orderings can give the same result, and the optimal assignment depends on the specific values and how they divide by different factors.

This leads us to model the problem as a bipartite matching problem:

One set of nodes represents the locks (with their strengths)
Another set represents the positions (1st, 2nd, 3rd, etc.)
The edge weight between lock i and position j is the time needed: ⌈strength[i] / (j+1)⌉
We need to find a perfect matching that minimizes the total weight

Since we need to minimize the total cost of matching all locks to all positions, this is a Minimum Cost Maximum Flow problem. The solution uses a specialized algorithm (Min Cost Flow) to efficiently find the optimal assignment without having to check all n! permutations.

The formula (a[i] - 1) // (j + 1) + 1 in the code is equivalent to ⌈a[i] / (j+1)⌉, calculating the ceiling division which gives us the exact number of minutes needed for lock i at position j.

Learn more about Depth-First Search and Graph patterns.

Solution Approach

The solution implements a Minimum Cost Maximum Flow (MCF) algorithm to solve this assignment problem optimally. Let's walk through how this sophisticated approach works:

Graph Construction

The solution creates a bipartite graph with a source and sink:

Source node s: Connected to all lock nodes
Lock nodes: Indices 0 to n-1 representing each lock
Position nodes: Indices n to 2n-1 representing each position in the sequence
Sink node t: Connected from all position nodes

n = len(a)
s = n * 2  # source node
t = s + 1  # sink node
g = MCFGraph(t + 1)  # create [graph](/problems/graph_intro) with all nodes

Edge Setup

Three types of edges are added:

Source to locks: g.add_edge(s, i, 1, 0) - capacity 1, cost 0
- Ensures each lock is selected exactly once
Locks to positions: g.add_edge(i, j + n, 1, (a[i] - 1) // (j + 1) + 1)
- Connects lock i to position j
- Capacity 1 (each assignment happens once)
- Cost is the time needed: ⌈a[i] / (j+1)⌉
- The formula (a[i] - 1) // (j + 1) + 1 computes ceiling division
Positions to sink: g.add_edge(i + n, t, 1, 0) - capacity 1, cost 0
- Ensures each position is filled exactly once

The MCF Algorithm

The MCFGraph class implements a cost-efficient flow algorithm using:

Dual variables and reduced costs: The algorithm maintains dual variables to transform the problem and find augmenting paths efficiently
Dijkstra-based path finding (refine_dual function):
- Uses a priority queue to find the shortest augmenting path
- Computes reduced costs: e.cost - dual[w] + dual[v]
- Updates dual variables to maintain optimality conditions
Flow augmentation:
- Finds minimum capacity along the path
- Updates capacities along the path and reverse edges
- Accumulates flow and cost
Iterative refinement:
- Continues finding augmenting paths until flow limit (n) is reached
- Each iteration finds a path that minimizes cost per unit flow

Final Result

The call g.flow(s, t, n)[1] returns:

Flow of n (ensuring all locks are broken)
Minimum total cost (the minimum time needed)

The algorithm guarantees finding the globally optimal assignment of locks to positions, avoiding the need to check all n! permutations. Instead, it runs in polynomial time, typically O(n³) for this bipartite matching scenario.

This approach is much more efficient than brute-force DFS/backtracking for larger values of n, though for very small inputs, a simple backtracking solution might be more straightforward to implement.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with locks of strength [5, 3, 8].

Step 1: Graph Construction We create a bipartite graph with:

Source node (s = 6)
Lock nodes (0, 1, 2) representing locks with strengths [5, 3, 8]
Position nodes (3, 4, 5) representing 1st, 2nd, and 3rd positions
Sink node (t = 7)

Step 2: Calculate Time Costs For each lock-position pair, we calculate the time needed:

Lock\Position	1st (X=1)	2nd (X=2)	3rd (X=3)
Lock 0 (str=5)	⌈5/1⌉ = 5	⌈5/2⌉ = 3	⌈5/3⌉ = 2
Lock 1 (str=3)	⌈3/1⌉ = 3	⌈3/2⌉ = 2	⌈3/3⌉ = 1
Lock 2 (str=8)	⌈8/1⌉ = 8	⌈8/2⌉ = 4	⌈8/3⌉ = 3

Step 3: Add Edges

Source → Locks: edges with capacity 1, cost 0
Locks → Positions: edges with capacity 1, cost = time from table above
Positions → Sink: edges with capacity 1, cost 0

Step 4: Run Min Cost Flow Algorithm The algorithm finds augmenting paths that minimize total cost:

First augmenting path might be: s → Lock 1 → Position 0 → t
- Assigns Lock 1 (strength 3) to 1st position
- Cost: 3 minutes
Second path: s → Lock 0 → Position 1 → t
- Assigns Lock 0 (strength 5) to 2nd position
- Cost: 3 minutes
Third path: s → Lock 2 → Position 2 → t
- Assigns Lock 2 (strength 8) to 3rd position
- Cost: 3 minutes

Step 5: Result The optimal assignment is:

1st position: Lock 1 (strength 3) → 3 minutes
2nd position: Lock 0 (strength 5) → 3 minutes
3rd position: Lock 2 (strength 8) → 3 minutes
Total time: 9 minutes

This is better than the naive sorted order [5, 3, 8] which would give:

1st: strength 5 → 5 minutes
2nd: strength 3 → 2 minutes
3rd: strength 8 → 3 minutes
Total: 10 minutes

The MCF algorithm found that putting the weakest lock first and strategically placing the medium-strength lock second (where it benefits from X=2) gives the optimal result.

Solution Implementation

1from typing import List, Tuple, Optional, NamedTuple, cast
2from heapq import heappush, heappop
3
4
5class MCFGraph:
6    """Minimum Cost Flow Graph implementation using successive shortest path algorithm."""
7  
8    class Edge(NamedTuple):
9        """Represents an edge in the original graph with flow information."""
10        src: int      # Source vertex
11        dst: int      # Destination vertex
12        cap: int      # Original capacity
13        flow: int     # Current flow through the edge
14        cost: int     # Cost per unit flow
15  
16    class _Edge:
17        """Internal edge representation for the residual graph."""
18        def __init__(self, dst: int, cap: int, cost: int) -> None:
19            self.dst = dst    # Destination vertex
20            self.cap = cap    # Residual capacity
21            self.cost = cost  # Cost per unit flow
22            self.rev: Optional['MCFGraph._Edge'] = None  # Reverse edge reference
23  
24    def __init__(self, n: int) -> None:
25        """Initialize a flow graph with n vertices."""
26        self._n = n  # Number of vertices
27        self._g: List[List[MCFGraph._Edge]] = [[] for _ in range(n)]  # Adjacency list
28        self._edges: List[MCFGraph._Edge] = []  # List of original edges
29  
30    def add_edge(self, src: int, dst: int, cap: int, cost: int) -> int:
31        """
32        Add an edge from src to dst with given capacity and cost.
33        Returns the index of the added edge.
34        """
35        assert 0 <= src < self._n
36        assert 0 <= dst < self._n
37        assert 0 <= cap
38      
39        edge_id = len(self._edges)
40      
41        # Create forward and reverse edges for residual graph
42        forward_edge = MCFGraph._Edge(dst, cap, cost)
43        reverse_edge = MCFGraph._Edge(src, 0, -cost)
44      
45        # Link forward and reverse edges
46        forward_edge.rev = reverse_edge
47        reverse_edge.rev = forward_edge
48      
49        # Add edges to adjacency list
50        self._g[src].append(forward_edge)
51        self._g[dst].append(reverse_edge)
52      
53        # Store original edge for reference
54        self._edges.append(forward_edge)
55      
56        return edge_id
57  
58    def get_edge(self, i: int) -> Edge:
59        """Get edge information by its index."""
60        assert 0 <= i < len(self._edges)
61      
62        edge = self._edges[i]
63        reverse_edge = cast(MCFGraph._Edge, edge.rev)
64      
65        # Calculate original capacity and current flow
66        original_capacity = edge.cap + reverse_edge.cap
67        current_flow = reverse_edge.cap
68      
69        return MCFGraph.Edge(
70            src=reverse_edge.dst,
71            dst=edge.dst,
72            cap=original_capacity,
73            flow=current_flow,
74            cost=edge.cost
75        )
76  
77    def edges(self) -> List[Edge]:
78        """Get all edges in the graph."""
79        return [self.get_edge(i) for i in range(len(self._edges))]
80  
81    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> Tuple[int, int]:
82        """
83        Find maximum flow from s to t with minimum cost.
84        Returns (flow_amount, total_cost).
85        """
86        return self.slope(s, t, flow_limit)[-1]
87  
88    def slope(
89        self, s: int, t: int, flow_limit: Optional[int] = None
90    ) -> List[Tuple[int, int]]:
91        """
92        Find the cost-flow curve from s to t.
93        Returns list of (flow, cost) pairs representing the piecewise linear function.
94        """
95        assert 0 <= s < self._n
96        assert 0 <= t < self._n
97        assert s != t
98      
99        # Set flow limit to sum of outgoing capacities from source if not specified
100        if flow_limit is None:
101            flow_limit = cast(int, sum(e.cap for e in self._g[s]))
102      
103        # Dual variables for reduced cost
104        dual = [0] * self._n
105        # Previous vertex and edge in shortest path
106        prev: List[Optional[Tuple[int, MCFGraph._Edge]]] = [None] * self._n
107      
108        def refine_dual() -> bool:
109            """
110            Find shortest path from s to t using Dijkstra's algorithm
111            and update dual variables. Returns True if path exists.
112            """
113            # Priority queue: (distance, vertex)
114            priority_queue = [(0, s)]
115            visited = [False] * self._n
116            dist: List[Optional[int]] = [None] * self._n
117            dist[s] = 0
118          
119            while priority_queue:
120                dist_v, v = heappop(priority_queue)
121              
122                if visited[v]:
123                    continue
124                visited[v] = True
125              
126                if v == t:
127                    break
128              
129                dual_v = dual[v]
130              
131                # Check all outgoing edges
132                for edge in self._g[v]:
133                    w = edge.dst
134                  
135                    # Skip if already visited or no residual capacity
136                    if visited[w] or edge.cap == 0:
137                        continue
138                  
139                    # Calculate reduced cost
140                    reduced_cost = edge.cost - dual[w] + dual_v
141                    new_dist = dist_v + reduced_cost
142                    dist_w = dist[w]
143                  
144                    # Update distance if shorter path found
145                    if dist_w is None or new_dist < dist_w:
146                        dist[w] = new_dist
147                        prev[w] = v, edge
148                        heappush(priority_queue, (new_dist, w))
149            else:
150                # No path to t found
151                return False
152          
153            # Update dual variables to maintain reduced costs
154            dist_t = dist[t]
155            for v in range(self._n):
156                if visited[v]:
157                    dual[v] -= cast(int, dist_t) - cast(int, dist[v])
158          
159            return True
160      
161        # Initialize flow and cost
162        total_flow = 0
163        total_cost = 0
164        prev_cost_per_flow: Optional[int] = None
165        result = [(total_flow, total_cost)]
166      
167        # Main loop: find augmenting paths until flow limit reached
168        while total_flow < flow_limit:
169            # Find shortest augmenting path
170            if not refine_dual():
171                break
172          
173            # Find bottleneck capacity along the path
174            bottleneck = flow_limit - total_flow
175            v = t
176            while prev[v] is not None:
177                u, edge = cast(Tuple[int, MCFGraph._Edge], prev[v])
178                bottleneck = min(bottleneck, edge.cap)
179                v = u
180          
181            # Update residual capacities along the path
182            v = t
183            while prev[v] is not None:
184                u, edge = cast(Tuple[int, MCFGraph._Edge], prev[v])
185                edge.cap -= bottleneck
186                assert edge.rev is not None
187                edge.rev.cap += bottleneck
188                v = u
189          
190            # Update flow and cost
191            cost_per_unit = -dual[s]
192            total_flow += bottleneck
193            total_cost += bottleneck * cost_per_unit
194          
195            # Merge with previous segment if same slope
196            if cost_per_unit == prev_cost_per_flow:
197                result.pop()
198          
199            result.append((total_flow, total_cost))
200            prev_cost_per_flow = cost_per_unit
201      
202        return result
203
204
205class Solution:
206    def findMinimumTime(self, a: List[int]) -> int:
207        """
208        Find minimum total time to process all tasks.
209        Each task i takes ceil(a[i]/(j+1)) time if assigned to worker j.
210        """
211        n = len(a)
212      
213        # Create bipartite graph with source and sink
214        source = n * 2  # Source node
215        sink = source + 1  # Sink node
216        graph = MCFGraph(sink + 1)
217      
218        # Build bipartite matching graph
219        for i in range(n):
220            # Connect source to each task with capacity 1
221            graph.add_edge(source, i, 1, 0)
222          
223            # Connect each worker to sink with capacity 1
224            graph.add_edge(i + n, sink, 1, 0)
225          
226            # Connect each task to each worker with appropriate cost
227            for j in range(n):
228                # Cost is the time task i takes on worker j
229                time_cost = (a[i] - 1) // (j + 1) + 1  # Equivalent to ceil(a[i]/(j+1))
230                graph.add_edge(i, j + n, 1, time_cost)
231      
232        # Find minimum cost perfect matching
233        _, min_cost = graph.flow(source, sink, n)
234        return min_cost
235

1import java.util.*;
2
3/**
4 * Minimum Cost Flow Graph implementation using the Successive Shortest Path algorithm.
5 * This class solves the minimum cost maximum flow problem on a directed graph.
6 */
7class MCFGraph {
8    /**
9     * Represents an edge in the flow network with source, destination, capacity, flow, and cost.
10     */
11    static class Edge {
12        int source;
13        int destination;
14        int capacity;
15        int flow;
16        int cost;
17
18        Edge(int source, int destination, int capacity, int flow, int cost) {
19            this.source = source;
20            this.destination = destination;
21            this.capacity = capacity;
22            this.flow = flow;
23            this.cost = cost;
24        }
25    }
26
27    /**
28     * Internal edge representation for the residual graph.
29     * Each edge maintains a reference to its reverse edge for efficient flow updates.
30     */
31    static class InternalEdge {
32        int destination;
33        int capacity;
34        int cost;
35        InternalEdge reverseEdge;
36
37        InternalEdge(int destination, int capacity, int cost) {
38            this.destination = destination;
39            this.capacity = capacity;
40            this.cost = cost;
41            this.reverseEdge = null;
42        }
43    }
44
45    /**
46     * Helper class to store a pair of vertex and its incoming edge in the shortest path.
47     */
48    static class VertexEdgePair {
49        int vertex;
50        InternalEdge edge;
51
52        VertexEdgePair(int vertex, InternalEdge edge) {
53            this.vertex = vertex;
54            this.edge = edge;
55        }
56    }
57
58    private int numberOfVertices;
59    private List<List<InternalEdge>> adjacencyList;
60    private List<InternalEdge> edgeList;
61
62    /**
63     * Constructs a minimum cost flow graph with n vertices.
64     * @param n the number of vertices in the graph
65     */
66    public MCFGraph(int n) {
67        this.numberOfVertices = n;
68        this.adjacencyList = new ArrayList<>();
69        this.edgeList = new ArrayList<>();
70      
71        // Initialize adjacency list for each vertex
72        for (int i = 0; i < n; i++) {
73            adjacencyList.add(new ArrayList<>());
74        }
75    }
76
77    /**
78     * Adds a directed edge from source to destination with given capacity and cost.
79     * @param src source vertex
80     * @param dst destination vertex
81     * @param cap edge capacity
82     * @param cost cost per unit flow
83     * @return the index of the added edge
84     */
85    public int addEdge(int src, int dst, int cap, int cost) {
86        // Validate input parameters
87        assert (0 <= src && src < numberOfVertices);
88        assert (0 <= dst && dst < numberOfVertices);
89        assert (0 <= cap);
90
91        int edgeIndex = edgeList.size();
92      
93        // Create forward and reverse edges for residual graph
94        InternalEdge forwardEdge = new InternalEdge(dst, cap, cost);
95        InternalEdge reverseEdge = new InternalEdge(src, 0, -cost);
96      
97        // Link forward and reverse edges
98        forwardEdge.reverseEdge = reverseEdge;
99        reverseEdge.reverseEdge = forwardEdge;
100
101        // Add edges to adjacency list
102        adjacencyList.get(src).add(forwardEdge);
103        adjacencyList.get(dst).add(reverseEdge);
104      
105        // Store the forward edge in edge list
106        edgeList.add(forwardEdge);
107      
108        return edgeIndex;
109    }
110
111    /**
112     * Retrieves the edge at the given index.
113     * @param i edge index
114     * @return Edge object with current flow information
115     */
116    public Edge getEdge(int i) {
117        assert (0 <= i && i < edgeList.size());
118      
119        InternalEdge forwardEdge = edgeList.get(i);
120        InternalEdge reverseEdge = forwardEdge.reverseEdge;
121      
122        // Calculate original capacity and current flow
123        int originalCapacity = forwardEdge.capacity + reverseEdge.capacity;
124        int currentFlow = reverseEdge.capacity;
125      
126        return new Edge(reverseEdge.destination, forwardEdge.destination, 
127                       originalCapacity, currentFlow, forwardEdge.cost);
128    }
129
130    /**
131     * Returns all edges in the graph.
132     * @return list of all edges with their current flow information
133     */
134    public List<Edge> edges() {
135        List<Edge> result = new ArrayList<>();
136        for (int i = 0; i < edgeList.size(); i++) {
137            result.add(getEdge(i));
138        }
139        return result;
140    }
141
142    /**
143     * Computes the minimum cost flow from source to sink with optional flow limit.
144     * @param s source vertex
145     * @param t sink vertex
146     * @param flowLimit maximum flow limit (null for unlimited)
147     * @return array containing [total flow, total cost]
148     */
149    public int[] flow(int s, int t, Integer flowLimit) {
150        List<int[]> slopeResult = slope(s, t, flowLimit);
151        return slopeResult.get(slopeResult.size() - 1);
152    }
153
154    /**
155     * Computes the slope function of minimum cost flow.
156     * Returns a sequence of [flow, cost] pairs representing the piecewise linear cost function.
157     * @param s source vertex
158     * @param t sink vertex
159     * @param flowLimit maximum flow limit (null for unlimited)
160     * @return list of [flow, cost] pairs
161     */
162    public List<int[]> slope(int s, int t, Integer flowLimit) {
163        // Validate input parameters
164        assert (0 <= s && s < numberOfVertices);
165        assert (0 <= t && t < numberOfVertices);
166        assert (s != t);
167
168        // Set flow limit to sum of outgoing capacities from source if not specified
169        if (flowLimit == null) {
170            flowLimit = adjacencyList.get(s).stream()
171                                    .mapToInt(e -> e.capacity)
172                                    .sum();
173        }
174
175        // Initialize dual variables and predecessor array
176        int[] dualVariables = new int[numberOfVertices];
177        VertexEdgePair[] predecessors = new VertexEdgePair[numberOfVertices];
178
179        // Initialize result with zero flow and cost
180        List<int[]> result = new ArrayList<>();
181        result.add(new int[] {0, 0});
182
183        // Main loop: find augmenting paths and update flow
184        while (true) {
185            // Find shortest path using reduced costs
186            if (!findShortestPath(s, t, dualVariables, predecessors)) {
187                break;
188            }
189
190            // Calculate bottleneck capacity along the path
191            int bottleneckFlow = flowLimit;
192            int currentVertex = t;
193            while (predecessors[currentVertex] != null) {
194                VertexEdgePair pair = predecessors[currentVertex];
195                int previousVertex = pair.vertex;
196                InternalEdge edge = pair.edge;
197                bottleneckFlow = Math.min(bottleneckFlow, edge.capacity);
198                currentVertex = previousVertex;
199            }
200
201            // Update flow along the path
202            currentVertex = t;
203            while (predecessors[currentVertex] != null) {
204                VertexEdgePair pair = predecessors[currentVertex];
205                int previousVertex = pair.vertex;
206                InternalEdge edge = pair.edge;
207                edge.capacity -= bottleneckFlow;
208                edge.reverseEdge.capacity += bottleneckFlow;
209                currentVertex = previousVertex;
210            }
211
212            // Calculate cost and update result
213            int unitCost = -dualVariables[s];
214            int[] previousResult = result.get(result.size() - 1);
215            result.add(new int[] {
216                previousResult[0] + bottleneckFlow,
217                previousResult[1] + bottleneckFlow * unitCost
218            });
219
220            // Remove redundant point if cost remains the same
221            if (result.size() >= 2) {
222                int[] lastPoint = result.get(result.size() - 1);
223                int[] secondLastPoint = result.get(result.size() - 2);
224                if (unitCost == (secondLastPoint[1] / secondLastPoint[0])) {
225                    result.remove(result.size() - 2);
226                }
227            }
228        }
229
230        return result;
231    }
232
233    /**
234     * Finds the shortest path from source to sink using Dijkstra's algorithm with reduced costs.
235     * Updates dual variables to maintain optimality conditions.
236     * @param s source vertex
237     * @param t sink vertex
238     * @param dualVariables array of dual variables
239     * @param predecessors array to store path information
240     * @return true if a path exists, false otherwise
241     */
242    private boolean findShortestPath(int s, int t, int[] dualVariables, VertexEdgePair[] predecessors) {
243        // Initialize priority queue for Dijkstra's algorithm
244        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(
245            Comparator.comparingInt(a -> a[0])
246        );
247        priorityQueue.add(new int[] {0, s});
248      
249        // Initialize tracking arrays
250        boolean[] visited = new boolean[numberOfVertices];
251        Integer[] distances = new Integer[numberOfVertices];
252        Arrays.fill(distances, null);
253        distances[s] = 0;
254
255        // Dijkstra's algorithm with reduced costs
256        while (!priorityQueue.isEmpty()) {
257            int[] current = priorityQueue.poll();
258            int currentDistance = current[0];
259            int currentVertex = current[1];
260
261            // Skip if already visited
262            if (visited[currentVertex]) continue;
263            visited[currentVertex] = true;
264
265            // Stop if we reached the sink
266            if (currentVertex == t) break;
267
268            // Explore neighbors
269            int currentDual = dualVariables[currentVertex];
270            for (InternalEdge edge : adjacencyList.get(currentVertex)) {
271                int neighbor = edge.destination;
272              
273                // Skip if visited or no capacity
274                if (visited[neighbor] || edge.capacity == 0) continue;
275
276                // Calculate reduced cost and new distance
277                int reducedCost = edge.cost - dualVariables[neighbor] + currentDual;
278                int newDistance = currentDistance + reducedCost;
279                Integer neighborDistance = distances[neighbor];
280
281                // Update if we found a shorter path
282                if (neighborDistance == null || newDistance < neighborDistance) {
283                    distances[neighbor] = newDistance;
284                    predecessors[neighbor] = new VertexEdgePair(currentVertex, edge);
285                    priorityQueue.add(new int[] {newDistance, neighbor});
286                }
287            }
288        }
289
290        // Check if sink is reachable
291        if (!visited[t]) return false;
292
293        // Update dual variables to maintain optimality
294        int sinkDistance = distances[t];
295        for (int vertex = 0; vertex < numberOfVertices; vertex++) {
296            if (visited[vertex]) {
297                dualVariables[vertex] -= sinkDistance - distances[vertex];
298            }
299        }
300
301        return true;
302    }
303}
304
305/**
306 * Solution class for the minimum time problem using minimum cost flow.
307 */
308class Solution {
309    /**
310     * Finds the minimum time to process all tasks with given strengths.
311     * Uses minimum cost flow to model the assignment problem.
312     * @param strength array of task strengths
313     * @return minimum total time
314     */
315    public int findMinimumTime(int[] strength) {
316        int n = strength.length;
317      
318        // Create super source and super sink vertices
319        int superSource = n * 2;
320        int superSink = superSource + 1;
321      
322        // Initialize minimum cost flow graph
323        MCFGraph graph = new MCFGraph(superSink + 1);
324
325        // Build the bipartite graph
326        for (int i = 0; i < n; i++) {
327            // Connect source to left side (tasks)
328            graph.addEdge(superSource, i, 1, 0);
329          
330            // Connect right side (positions) to sink
331            graph.addEdge(i + n, superSink, 1, 0);
332          
333            // Connect each task to each position with appropriate cost
334            for (int j = 0; j < n; j++) {
335                // Cost represents time to complete task i at position j
336                int timeCost = (strength[i] - 1) / (j + 1) + 1;
337                graph.addEdge(i, j + n, 1, timeCost);
338            }
339        }
340
341        // Find minimum cost flow and return the total cost
342        return graph.flow(superSource, superSink, n)[1];
343    }
344}
345

1#include <vector>
2#include <queue>
3#include <algorithm>
4#include <limits>
5#include <cassert>
6
7using namespace std;
8
9/**
10 * Minimum Cost Flow Graph implementation using the Successive Shortest Path algorithm.
11 * This class solves the minimum cost maximum flow problem on a directed graph.
12 */
13class MCFGraph {
14public:
15    /**
16     * Represents an edge in the flow network with source, destination, capacity, flow, and cost.
17     */
18    struct Edge {
19        int source;
20        int destination;
21        int capacity;
22        int flow;
23        int cost;
24
25        Edge(int src, int dst, int cap, int flw, int cst) 
26            : source(src), destination(dst), capacity(cap), flow(flw), cost(cst) {}
27    };
28
29private:
30    /**
31     * Internal edge representation for the residual graph.
32     * Each edge maintains a reference to its reverse edge for efficient flow updates.
33     */
34    struct InternalEdge {
35        int destination;
36        int capacity;
37        int cost;
38        InternalEdge* reverse_edge;
39
40        InternalEdge(int dst, int cap, int cst) 
41            : destination(dst), capacity(cap), cost(cst), reverse_edge(nullptr) {}
42    };
43
44    /**
45     * Helper class to store a pair of vertex and its incoming edge in the shortest path.
46     */
47    struct VertexEdgePair {
48        int vertex;
49        InternalEdge* edge;
50
51        VertexEdgePair() : vertex(-1), edge(nullptr) {}
52        VertexEdgePair(int v, InternalEdge* e) : vertex(v), edge(e) {}
53    };
54
55    int number_of_vertices;
56    vector<vector<InternalEdge*>> adjacency_list;
57    vector<InternalEdge*> edge_list;
58
59public:
60    /**
61     * Constructs a minimum cost flow graph with n vertices.
62     * @param n the number of vertices in the graph
63     */
64    MCFGraph(int n) : number_of_vertices(n), adjacency_list(n) {}
65
66    /**
67     * Destructor to clean up dynamically allocated edges
68     */
69    ~MCFGraph() {
70        for (auto& edges : adjacency_list) {
71            for (auto* edge : edges) {
72                delete edge;
73            }
74        }
75    }
76
77    /**
78     * Adds a directed edge from source to destination with given capacity and cost.
79     * @param src source vertex
80     * @param dst destination vertex
81     * @param cap edge capacity
82     * @param cost cost per unit flow
83     * @return the index of the added edge
84     */
85    int addEdge(int src, int dst, int cap, int cost) {
86        // Validate input parameters
87        assert(0 <= src && src < number_of_vertices);
88        assert(0 <= dst && dst < number_of_vertices);
89        assert(0 <= cap);
90
91        int edge_index = edge_list.size();
92      
93        // Create forward and reverse edges for residual graph
94        InternalEdge* forward_edge = new InternalEdge(dst, cap, cost);
95        InternalEdge* reverse_edge = new InternalEdge(src, 0, -cost);
96      
97        // Link forward and reverse edges
98        forward_edge->reverse_edge = reverse_edge;
99        reverse_edge->reverse_edge = forward_edge;
100
101        // Add edges to adjacency list
102        adjacency_list[src].push_back(forward_edge);
103        adjacency_list[dst].push_back(reverse_edge);
104      
105        // Store the forward edge in edge list
106        edge_list.push_back(forward_edge);
107      
108        return edge_index;
109    }
110
111    /**
112     * Retrieves the edge at the given index.
113     * @param i edge index
114     * @return Edge object with current flow information
115     */
116    Edge getEdge(int i) {
117        assert(0 <= i && i < edge_list.size());
118      
119        InternalEdge* forward_edge = edge_list[i];
120        InternalEdge* reverse_edge = forward_edge->reverse_edge;
121      
122        // Calculate original capacity and current flow
123        int original_capacity = forward_edge->capacity + reverse_edge->capacity;
124        int current_flow = reverse_edge->capacity;
125      
126        return Edge(reverse_edge->destination, forward_edge->destination, 
127                   original_capacity, current_flow, forward_edge->cost);
128    }
129
130    /**
131     * Returns all edges in the graph.
132     * @return vector of all edges with their current flow information
133     */
134    vector<Edge> edges() {
135        vector<Edge> result;
136        for (int i = 0; i < edge_list.size(); i++) {
137            result.push_back(getEdge(i));
138        }
139        return result;
140    }
141
142    /**
143     * Computes the minimum cost flow from source to sink with optional flow limit.
144     * @param s source vertex
145     * @param t sink vertex
146     * @param flow_limit maximum flow limit (-1 for unlimited)
147     * @return pair containing [total flow, total cost]
148     */
149    pair<int, int> flow(int s, int t, int flow_limit = -1) {
150        vector<pair<int, int>> slope_result = slope(s, t, flow_limit);
151        return slope_result.back();
152    }
153
154    /**
155     * Computes the slope function of minimum cost flow.
156     * Returns a sequence of [flow, cost] pairs representing the piecewise linear cost function.
157     * @param s source vertex
158     * @param t sink vertex
159     * @param flow_limit maximum flow limit (-1 for unlimited)
160     * @return vector of [flow, cost] pairs
161     */
162    vector<pair<int, int>> slope(int s, int t, int flow_limit = -1) {
163        // Validate input parameters
164        assert(0 <= s && s < number_of_vertices);
165        assert(0 <= t && t < number_of_vertices);
166        assert(s != t);
167
168        // Set flow limit to sum of outgoing capacities from source if not specified
169        if (flow_limit == -1) {
170            flow_limit = 0;
171            for (auto* edge : adjacency_list[s]) {
172                flow_limit += edge->capacity;
173            }
174        }
175
176        // Initialize dual variables and predecessor array
177        vector<int> dual_variables(number_of_vertices, 0);
178        vector<VertexEdgePair> predecessors(number_of_vertices);
179
180        // Initialize result with zero flow and cost
181        vector<pair<int, int>> result;
182        result.push_back({0, 0});
183
184        // Main loop: find augmenting paths and update flow
185        while (flow_limit > 0) {
186            // Find shortest path using reduced costs
187            if (!findShortestPath(s, t, dual_variables, predecessors)) {
188                break;
189            }
190
191            // Calculate bottleneck capacity along the path
192            int bottleneck_flow = flow_limit;
193            int current_vertex = t;
194            while (predecessors[current_vertex].edge != nullptr) {
195                VertexEdgePair& pair = predecessors[current_vertex];
196                int previous_vertex = pair.vertex;
197                InternalEdge* edge = pair.edge;
198                bottleneck_flow = min(bottleneck_flow, edge->capacity);
199                current_vertex = previous_vertex;
200            }
201
202            // Update flow along the path
203            current_vertex = t;
204            while (predecessors[current_vertex].edge != nullptr) {
205                VertexEdgePair& pair = predecessors[current_vertex];
206                int previous_vertex = pair.vertex;
207                InternalEdge* edge = pair.edge;
208                edge->capacity -= bottleneck_flow;
209                edge->reverse_edge->capacity += bottleneck_flow;
210                current_vertex = previous_vertex;
211            }
212
213            // Calculate cost and update result
214            int unit_cost = -dual_variables[s];
215            pair<int, int> previous_result = result.back();
216            result.push_back({
217                previous_result.first + bottleneck_flow,
218                previous_result.second + bottleneck_flow * unit_cost
219            });
220
221            // Update flow limit
222            flow_limit -= bottleneck_flow;
223
224            // Remove redundant point if cost remains the same
225            if (result.size() >= 2) {
226                pair<int, int>& last_point = result.back();
227                pair<int, int>& second_last_point = result[result.size() - 2];
228                if (result.size() >= 3) {
229                    pair<int, int>& third_last_point = result[result.size() - 3];
230                    // Check if the slope is the same
231                    long long slope1 = (long long)(second_last_point.second - third_last_point.second);
232                    long long slope2 = (long long)(last_point.second - second_last_point.second);
233                    long long flow1 = second_last_point.first - third_last_point.first;
234                    long long flow2 = last_point.first - second_last_point.first;
235                    if (slope1 * flow2 == slope2 * flow1) {
236                        result.erase(result.end() - 2);
237                    }
238                }
239            }
240        }
241
242        return result;
243    }
244
245private:
246    /**
247     * Finds the shortest path from source to sink using Dijkstra's algorithm with reduced costs.
248     * Updates dual variables to maintain optimality conditions.
249     * @param s source vertex
250     * @param t sink vertex
251     * @param dual_variables array of dual variables
252     * @param predecessors array to store path information
253     * @return true if a path exists, false otherwise
254     */
255    bool findShortestPath(int s, int t, vector<int>& dual_variables, vector<VertexEdgePair>& predecessors) {
256        // Initialize priority queue for Dijkstra's algorithm
257        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> priority_queue;
258        priority_queue.push({0, s});
259      
260        // Initialize tracking arrays
261        vector<bool> visited(number_of_vertices, false);
262        vector<int> distances(number_of_vertices, numeric_limits<int>::max());
263        distances[s] = 0;
264
265        // Reset predecessors
266        fill(predecessors.begin(), predecessors.end(), VertexEdgePair());
267
268        // Dijkstra's algorithm with reduced costs
269        while (!priority_queue.empty()) {
270            auto [current_distance, current_vertex] = priority_queue.top();
271            priority_queue.pop();
272
273            // Skip if already visited
274            if (visited[current_vertex]) continue;
275            visited[current_vertex] = true;
276
277            // Stop if we reached the sink
278            if (current_vertex == t) break;
279
280            // Explore neighbors
281            int current_dual = dual_variables[current_vertex];
282            for (InternalEdge* edge : adjacency_list[current_vertex]) {
283                int neighbor = edge->destination;
284              
285                // Skip if visited or no capacity
286                if (visited[neighbor] || edge->capacity == 0) continue;
287
288                // Calculate reduced cost and new distance
289                int reduced_cost = edge->cost - dual_variables[neighbor] + current_dual;
290                int new_distance = current_distance + reduced_cost;
291
292                // Update if we found a shorter path
293                if (new_distance < distances[neighbor]) {
294                    distances[neighbor] = new_distance;
295                    predecessors[neighbor] = VertexEdgePair(current_vertex, edge);
296                    priority_queue.push({new_distance, neighbor});
297                }
298            }
299        }
300
301        // Check if sink is reachable
302        if (!visited[t]) return false;
303
304        // Update dual variables to maintain optimality
305        int sink_distance = distances[t];
306        for (int vertex = 0; vertex < number_of_vertices; vertex++) {
307            if (visited[vertex]) {
308                dual_variables[vertex] -= sink_distance - distances[vertex];
309            }
310        }
311
312        return true;
313    }
314};
315
316/**
317 * Solution class for the minimum time problem using minimum cost flow.
318 */
319class Solution {
320public:
321    /**
322     * Finds the minimum time to process all tasks with given strengths.
323     * Uses minimum cost flow to model the assignment problem.
324     * @param strength array of task strengths
325     * @return minimum total time
326     */
327    int findMinimumTime(vector<int>& strength) {
328        int n = strength.size();
329      
330        // Create super source and super sink vertices
331        int super_source = n * 2;
332        int super_sink = super_source + 1;
333      
334        // Initialize minimum cost flow graph
335        MCFGraph graph(super_sink + 1);
336
337        // Build the bipartite graph
338        for (int i = 0; i < n; i++) {
339            // Connect source to left side (tasks)
340            graph.addEdge(super_source, i, 1, 0);
341          
342            // Connect right side (positions) to sink
343            graph.addEdge(i + n, super_sink, 1, 0);
344          
345            // Connect each task to each position with appropriate cost
346            for (int j = 0; j < n; j++) {
347                // Cost represents time to complete task i at position j
348                int time_cost = (strength[i] - 1) / (j + 1) + 1;
349                graph.addEdge(i, j + n, 1, time_cost);
350            }
351        }
352
353        // Find minimum cost flow and return the total cost
354        return graph.flow(super_source, super_sink, n).second;
355    }
356};
357

1/**
2 * Represents an edge in the flow network with source, destination, capacity, flow, and cost.
3 */
4interface Edge {
5    source: number;
6    destination: number;
7    capacity: number;
8    flow: number;
9    cost: number;
10}
11
12/**
13 * Internal edge representation for the residual graph.
14 * Each edge maintains a reference to its reverse edge for efficient flow updates.
15 */
16class InternalEdge {
17    destination: number;
18    capacity: number;
19    cost: number;
20    reverseEdge: InternalEdge | null;
21
22    constructor(destination: number, capacity: number, cost: number) {
23        this.destination = destination;
24        this.capacity = capacity;
25        this.cost = cost;
26        this.reverseEdge = null;
27    }
28}
29
30/**
31 * Helper class to store a pair of vertex and its incoming edge in the shortest path.
32 */
33interface VertexEdgePair {
34    vertex: number;
35    edge: InternalEdge;
36}
37
38// Global variables for the MCF graph
39let numberOfVertices: number;
40let adjacencyList: InternalEdge[][];
41let edgeList: InternalEdge[];
42
43/**
44 * Initializes a minimum cost flow graph with n vertices.
45 * @param n - The number of vertices in the graph
46 */
47function initializeMCFGraph(n: number): void {
48    numberOfVertices = n;
49    adjacencyList = [];
50    edgeList = [];
51  
52    // Initialize adjacency list for each vertex
53    for (let i = 0; i < n; i++) {
54        adjacencyList.push([]);
55    }
56}
57
58/**
59 * Adds a directed edge from source to destination with given capacity and cost.
60 * @param src - Source vertex
61 * @param dst - Destination vertex
62 * @param cap - Edge capacity
63 * @param cost - Cost per unit flow
64 * @returns The index of the added edge
65 */
66function addEdge(src: number, dst: number, cap: number, cost: number): number {
67    // Validate input parameters
68    if (src < 0 || src >= numberOfVertices || dst < 0 || dst >= numberOfVertices || cap < 0) {
69        throw new Error("Invalid edge parameters");
70    }
71
72    const edgeIndex = edgeList.length;
73  
74    // Create forward and reverse edges for residual graph
75    const forwardEdge = new InternalEdge(dst, cap, cost);
76    const reverseEdge = new InternalEdge(src, 0, -cost);
77  
78    // Link forward and reverse edges
79    forwardEdge.reverseEdge = reverseEdge;
80    reverseEdge.reverseEdge = forwardEdge;
81
82    // Add edges to adjacency list
83    adjacencyList[src].push(forwardEdge);
84    adjacencyList[dst].push(reverseEdge);
85  
86    // Store the forward edge in edge list
87    edgeList.push(forwardEdge);
88  
89    return edgeIndex;
90}
91
92/**
93 * Retrieves the edge at the given index.
94 * @param i - Edge index
95 * @returns Edge object with current flow information
96 */
97function getEdge(i: number): Edge {
98    if (i < 0 || i >= edgeList.length) {
99        throw new Error("Invalid edge index");
100    }
101  
102    const forwardEdge = edgeList[i];
103    const reverseEdge = forwardEdge.reverseEdge!;
104  
105    // Calculate original capacity and current flow
106    const originalCapacity = forwardEdge.capacity + reverseEdge.capacity;
107    const currentFlow = reverseEdge.capacity;
108  
109    return {
110        source: reverseEdge.destination,
111        destination: forwardEdge.destination,
112        capacity: originalCapacity,
113        flow: currentFlow,
114        cost: forwardEdge.cost
115    };
116}
117
118/**
119 * Returns all edges in the graph.
120 * @returns List of all edges with their current flow information
121 */
122function edges(): Edge[] {
123    const result: Edge[] = [];
124    for (let i = 0; i < edgeList.length; i++) {
125        result.push(getEdge(i));
126    }
127    return result;
128}
129
130/**
131 * Finds the shortest path from source to sink using Dijkstra's algorithm with reduced costs.
132 * Updates dual variables to maintain optimality conditions.
133 * @param s - Source vertex
134 * @param t - Sink vertex
135 * @param dualVariables - Array of dual variables
136 * @param predecessors - Array to store path information
137 * @returns True if a path exists, false otherwise
138 */
139function findShortestPath(
140    s: number, 
141    t: number, 
142    dualVariables: number[], 
143    predecessors: (VertexEdgePair | null)[]
144): boolean {
145    // Initialize priority queue for Dijkstra's algorithm
146    const priorityQueue: Array<[number, number]> = [[0, s]];
147  
148    // Initialize tracking arrays
149    const visited: boolean[] = new Array(numberOfVertices).fill(false);
150    const distances: (number | null)[] = new Array(numberOfVertices).fill(null);
151    distances[s] = 0;
152
153    // Dijkstra's algorithm with reduced costs
154    while (priorityQueue.length > 0) {
155        // Sort to get minimum distance element (simulating priority queue)
156        priorityQueue.sort((a, b) => a[0] - b[0]);
157        const [currentDistance, currentVertex] = priorityQueue.shift()!;
158
159        // Skip if already visited
160        if (visited[currentVertex]) continue;
161        visited[currentVertex] = true;
162
163        // Stop if we reached the sink
164        if (currentVertex === t) break;
165
166        // Explore neighbors
167        const currentDual = dualVariables[currentVertex];
168        for (const edge of adjacencyList[currentVertex]) {
169            const neighbor = edge.destination;
170          
171            // Skip if visited or no capacity
172            if (visited[neighbor] || edge.capacity === 0) continue;
173
174            // Calculate reduced cost and new distance
175            const reducedCost = edge.cost - dualVariables[neighbor] + currentDual;
176            const newDistance = currentDistance + reducedCost;
177            const neighborDistance = distances[neighbor];
178
179            // Update if we found a shorter path
180            if (neighborDistance === null || newDistance < neighborDistance) {
181                distances[neighbor] = newDistance;
182                predecessors[neighbor] = { vertex: currentVertex, edge: edge };
183                priorityQueue.push([newDistance, neighbor]);
184            }
185        }
186    }
187
188    // Check if sink is reachable
189    if (!visited[t]) return false;
190
191    // Update dual variables to maintain optimality
192    const sinkDistance = distances[t]!;
193    for (let vertex = 0; vertex < numberOfVertices; vertex++) {
194        if (visited[vertex]) {
195            dualVariables[vertex] -= sinkDistance - distances[vertex]!;
196        }
197    }
198
199    return true;
200}
201
202/**
203 * Computes the slope function of minimum cost flow.
204 * Returns a sequence of [flow, cost] pairs representing the piecewise linear cost function.
205 * @param s - Source vertex
206 * @param t - Sink vertex
207 * @param flowLimit - Maximum flow limit (null for unlimited)
208 * @returns List of [flow, cost] pairs
209 */
210function slope(s: number, t: number, flowLimit: number | null): number[][] {
211    // Validate input parameters
212    if (s < 0 || s >= numberOfVertices || t < 0 || t >= numberOfVertices || s === t) {
213        throw new Error("Invalid source or sink vertex");
214    }
215
216    // Set flow limit to sum of outgoing capacities from source if not specified
217    if (flowLimit === null) {
218        flowLimit = adjacencyList[s].reduce((sum, edge) => sum + edge.capacity, 0);
219    }
220
221    // Initialize dual variables and predecessor array
222    const dualVariables: number[] = new Array(numberOfVertices).fill(0);
223    const predecessors: (VertexEdgePair | null)[] = new Array(numberOfVertices).fill(null);
224
225    // Initialize result with zero flow and cost
226    const result: number[][] = [[0, 0]];
227
228    // Main loop: find augmenting paths and update flow
229    while (true) {
230        // Clear predecessors for new iteration
231        predecessors.fill(null);
232      
233        // Find shortest path using reduced costs
234        if (!findShortestPath(s, t, dualVariables, predecessors)) {
235            break;
236        }
237
238        // Calculate bottleneck capacity along the path
239        let bottleneckFlow = flowLimit;
240        let currentVertex = t;
241        while (predecessors[currentVertex] !== null) {
242            const pair = predecessors[currentVertex]!;
243            const edge = pair.edge;
244            bottleneckFlow = Math.min(bottleneckFlow, edge.capacity);
245            currentVertex = pair.vertex;
246        }
247
248        // Update flow along the path
249        currentVertex = t;
250        while (predecessors[currentVertex] !== null) {
251            const pair = predecessors[currentVertex]!;
252            const edge = pair.edge;
253            edge.capacity -= bottleneckFlow;
254            edge.reverseEdge!.capacity += bottleneckFlow;
255            currentVertex = pair.vertex;
256        }
257
258        // Calculate cost and update result
259        const unitCost = -dualVariables[s];
260        const previousResult = result[result.length - 1];
261        result.push([
262            previousResult[0] + bottleneckFlow,
263            previousResult[1] + bottleneckFlow * unitCost
264        ]);
265
266        // Remove redundant point if cost remains the same
267        if (result.length >= 2) {
268            const lastPoint = result[result.length - 1];
269            const secondLastPoint = result[result.length - 2];
270            if (secondLastPoint[0] > 0 && unitCost === Math.floor(secondLastPoint[1] / secondLastPoint[0])) {
271                result.splice(result.length - 2, 1);
272            }
273        }
274    }
275
276    return result;
277}
278
279/**
280 * Computes the minimum cost flow from source to sink with optional flow limit.
281 * @param s - Source vertex
282 * @param t - Sink vertex
283 * @param flowLimit - Maximum flow limit (null for unlimited)
284 * @returns Array containing [total flow, total cost]
285 */
286function flow(s: number, t: number, flowLimit: number | null): number[] {
287    const slopeResult = slope(s, t, flowLimit);
288    return slopeResult[slopeResult.length - 1];
289}
290
291/**
292 * Finds the minimum time to process all tasks with given strengths.
293 * Uses minimum cost flow to model the assignment problem.
294 * @param strength - Array of task strengths
295 * @returns Minimum total time
296 */
297function findMinimumTime(strength: number[]): number {
298    const n = strength.length;
299  
300    // Create super source and super sink vertices
301    const superSource = n * 2;
302    const superSink = superSource + 1;
303  
304    // Initialize minimum cost flow graph
305    initializeMCFGraph(superSink + 1);
306
307    // Build the bipartite graph
308    for (let i = 0; i < n; i++) {
309        // Connect source to left side (tasks)
310        addEdge(superSource, i, 1, 0);
311      
312        // Connect right side (positions) to sink
313        addEdge(i + n, superSink, 1, 0);
314      
315        // Connect each task to each position with appropriate cost
316        for (let j = 0; j < n; j++) {
317            // Cost represents time to complete task i at position j
318            const timeCost = Math.floor((strength[i] - 1) / (j + 1)) + 1;
319            addEdge(i, j + n, 1, timeCost);
320        }
321    }
322
323    // Find minimum cost flow and return the total cost
324    return flow(superSource, superSink, n)[1];
325}
326

Time and Space Complexity

Time Complexity: O(n^3 log n)

The solution uses a Min-Cost Max-Flow algorithm to solve the problem. Breaking down the complexity:

Graph Construction:
- The graph has 2n + 2 vertices (n source nodes, n sink nodes, plus super source and super sink)
- Edge creation: O(n^2) edges are added (each of n workers to n positions)
- Each add_edge operation is O(1)
- Total graph construction: O(n^2)
Min-Cost Flow Algorithm:
- The flow() method calls slope() which uses successive shortest path algorithm
- The algorithm finds augmenting paths up to n times (maximum flow is n)
- Each iteration of finding an augmenting path:
  - Uses Dijkstra's algorithm with a priority queue: O((V + E) log V)
  - With V = 2n + 2 vertices and E = O(n^2) edges
  - Each shortest path computation: O(n^2 log n)
- Total for flow computation: O(n × n^2 log n) = O(n^3 log n)

Overall time complexity: O(n^2) + O(n^3 log n) = O(n^3 log n)

Space Complexity: O(n^2)

Graph Storage:
- Adjacency list _g: stores O(n^2) edges (forward and reverse edges)
- Edge list _edges: stores O(n^2) edge references
- Graph space: O(n^2)
Algorithm Working Space:
- Arrays dual, prev, dist, visited: each O(n) size
- Priority queue: at most O(n) elements
- Working space: O(n)

Overall space complexity: O(n^2) + O(n) = O(n^2)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Cost Calculation for Lock-Position Assignment

One of the most common mistakes is incorrectly calculating the time needed to break a lock at a given position. The formula for computing the ceiling division can be error-prone.

Pitfall Example:

# Incorrect: Using regular division and ceiling
time_cost = math.ceil(a[i] / (j + 1))  # Requires import math

# Incorrect: Simple integer division (floors instead of ceiling)
time_cost = a[i] // (j + 1)  # This gives floor, not ceiling!

# Incorrect: Off-by-one error in position indexing
time_cost = (a[i] - 1) // j + 1  # j should be j+1 since positions start at 0

Correct Solution:

# Correct ceiling division formula
time_cost = (a[i] - 1) // (j + 1) + 1
# This works because: ceil(a/b) = floor((a-1)/b) + 1 for positive integers

2. Graph Structure Confusion

The bipartite graph structure can be confusing, leading to incorrect node indexing or edge connections.

Pitfall Example:

# Incorrect: Mixing up node indices
for i in range(n):
    # Wrong: connecting task directly to sink
    graph.add_edge(i, sink, 1, 0)  
  
    # Wrong: incorrect position node indexing
    for j in range(n):
        graph.add_edge(i, j, 1, time_cost)  # Should be j+n for position nodes

Correct Solution:

# Maintain clear separation of node types:
# - Tasks: indices 0 to n-1
# - Positions: indices n to 2n-1
# - Source: index 2n
# - Sink: index 2n+1

for i in range(n):
    graph.add_edge(source, i, 1, 0)           # source to task
    graph.add_edge(i + n, sink, 1, 0)         # position to sink
    for j in range(n):
        graph.add_edge(i, j + n, 1, time_cost) # task to position

3. Misunderstanding the Problem's Sequential Nature

A critical misunderstanding is thinking that the factor X depends on which lock is broken rather than the position in the sequence.

Pitfall Example:

# Incorrect: Thinking X is tied to the lock index
def calculate_time(lock_strength, lock_index):
    return (lock_strength - 1) // (lock_index + 1) + 1  # Wrong!

Correct Understanding:

The factor X = 1 for the first lock broken (regardless of which lock it is)
The factor X = 2 for the second lock broken
The factor X = j+1 for the lock broken at position j (0-indexed)

4. Over-Engineering with Complex MCF for Small Inputs

While the MCF solution is elegant and optimal, it's overkill for small inputs where a simple permutation approach would suffice.

Alternative for Small n (≤ 10):

from itertools import permutations

def findMinimumTime_simple(a: List[int]) -> int:
    n = len(a)
    if n <= 10:  # Use brute force for small inputs
        min_time = float('inf')
        for perm in permutations(range(n)):
            time = sum((a[perm[j]] - 1) // (j + 1) + 1 for j in range(n))
            min_time = min(min_time, time)
        return min_time
    # Fall back to MCF for larger inputs

5. Not Handling Edge Cases

Pitfall Example:

def findMinimumTime(a: List[int]) -> int:
    # Missing edge case checks
    n = len(a)  # What if a is empty?
    # What if a contains 0 or negative values?

Correct Solution:

def findMinimumTime(a: List[int]) -> int:
    if not a:
        return 0
  
    n = len(a)
    # Validate input assumptions
    assert all(strength > 0 for strength in a), "All lock strengths must be positive"
  
    # ... rest of the solution

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Fast-slow pointers

Two pointers moving in opposite direction

Binary search

Depth first search

I don't know

3385. Minimum Time to Break Locks II 🔒

Problem Description

Flowchart Walkthrough

Intuition

Solution Approach

Graph Construction

Edge Setup

The MCF Algorithm

Final Result

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Incorrect Cost Calculation for Lock-Position Assignment

2. Graph Structure Confusion

3. Misunderstanding the Problem's Sequential Nature

4. Over-Engineering with Complex MCF for Small Inputs

5. Not Handling Edge Cases

Recommended Readings