Join Us
Loading Similar Posts
Entering edit mode
Problem 1 : Index Difference
Solution: Hashing with Frequency Arrays
This is the most efficient solution for this problem, leveraging the constraint that the values of the array elements are small (1 <= arr[i] <= 2000). The core idea is to pre-calculate the first and last indices of every possible number in a single pass through the input array. By using arrays as direct-access hash tables, we can avoid the overhead of a map and achieve a very fast, linear-time solution.
The logic is as follows:
Utilize Constraints: Since the maximum value of an element is 2000, we can create two arrays,
first_occurrenceandlast_occurrence, of size 2001 to store the indices. This is more efficient than using a standard hash map.Initialization: Initialize the
first_occurrencearray with a sentinel value (e.g., -1) to indicate that no number has been seen yet. Thelast_occurrencearray can be initialized to 0.Single Pass Population: Iterate through the input array
arrfrom left to right (from indexi = 0ton-1). For each elementnum = arr[i]:If
first_occurrence[num]is still -1, it means this is the first time we are encountering this number. Record its index:first_occurrence[num] = i.For every occurrence of
num, update its last known position:last_occurrence[num] = i.
Construct Final Output: After the first pass, the
first_occurrenceandlast_occurrencearrays are fully populated. Iterate through the original input arrayarra second time. For each elementarr[i], look up its first and last indices from our arrays and calculate the difference:last_occurrence[arr[i]] - first_occurrence[arr[i]]. Print these results space-separated.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> arr(n);
unordered_map<int, int> first, last;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
if (first.find(arr[i]) == first.end()) {
first[arr[i]] = i;
}
last[arr[i]] = i;
}
for (int i = 0; i < n; ++i) {
cout << (last[arr[i]] - first[arr[i]]) << " ";
}
return 0;
}
Complexity Analysis:
Time Complexity: O(N + M). Where
Nis the number of elements in the input array andMis the maximum possible value of an element (2001). The algorithm involves two passes over the input array of sizeN. SinceMis a fixed constant, the complexity is effectively linear, orO(N).Space Complexity: O(M). The space is dominated by the
first_occurrenceandlast_occurrencearrays. Since their sizeMis constant and does not depend on the input sizeN, the space complexity isO(1)relative toN.
Entering edit mode
Problem 2: Shortest Driving Routes
Solution: Dijkstra's Algorithm
This is a classic Single-Source Shortest Path (SSSP) problem on a weighted, directed graph. The goal is to find the shortest path from a single starting point (the main office, node 1) to all other points. Dijkstra's algorithm is the standard and most efficient method for this task, especially since all route lengths (edge weights) are positive.
The logic is as follows:
Graph Representation: The city's pickup points and routes are modeled as a graph, where points are vertices and routes are weighted, directed edges. An adjacency list is used for efficient storage, where
adj[u]holds a list of pairs{v, w}, indicating a route fromutovwith lengthw.Initialization: A distance array,
dist, is created to store the shortest known distance from the main office (node 1) to every other pickup point. It's initialized with infinity for all points, except for the main office itself, whose distance is 0 (dist[1] = 0).Priority Queue for Efficiency: A min-priority queue is used to keep track of the next point to visit. It stores pairs of
{distance, point}and always prioritizes the point with the smallest distance from the source. This ensures that we always explore from the closest available point, which is the core of Dijkstra's algorithm.Iterative Path Relaxation: The algorithm iteratively extracts the closest point
ufrom the priority queue. For each of its neighborsv, it checks if the path throughuis shorter than the currently known path tov(i.e., ifdist[u] + weight(u,v) < dist[v]).Updating Distances: If a shorter path is found, the distance to
vis updated (dist[v] = dist[u] + weight(u,v)), and the new, shorter path information{dist[v], v}is added to the priority queue. This process continues until the priority queue is empty, by which time thedistarray will contain the shortest path lengths from the main office to all other points.
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
const long long INF = std::numeric_limits<long long>::max();
void solveShortestRoutes(int n, const std::vector<std::vector<std::pair<int, int>>>& adj) {
std::vector<long long> dist(n + 1, INF);
dist[1] = 0;
// Min-priority queue stores {distance, node}
std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> pq;
pq.push({0, 1});
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
// If we've found a shorter path already, skip this one
if (d > dist[u]) {
continue;
}
// Explore neighbors of the current node u
for (auto& edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
// If a shorter path to v is found through u, update it
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
// Print the shortest distances from the main office (node 1)
for (int i = 1; i <= n; ++i) {
std::cout << dist[i] << (i == n? "" : " ");
}
std::cout << std::endl;
}
// Example usage
// int main() {
// int n, m;
// std::cin >> n >> m;
// std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
// for (int i = 0; i < m; ++i) {
// int u, v, w;
// std::cin >> u >> v >> w;
// adj[u].push_back({v, w});
// }
// solveShortestRoutes(n, adj);
// return 0;
// }Complexity Analysis:
Time Complexity: O(M log N). The algorithm iterates through each connection (edge) once. For each edge that results in a shorter path, an operation (push) is performed on the priority queue, which takes O(log N) time, where N is the number of pickup points (vertices) and M is the number of connections. The complexity is dominated by these priority queue operations.
Space Complexity: O(N + M). The space is required to store the graph's adjacency list (O(N + M)) and the distance array (O(N)). The priority queue can, in the worst case, hold an entry for each vertex, contributing O(N) space.
