leetcode

commit 65c154a2ba279c85216dac7a1a2e1a087836153f
parent 222dc17f88ba6672609f9ea009d251eb681468bd
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  5 Mar 2023 17:59:33 +0100

Daily Problem

Diffstat:
A
Problems/1345.cpp
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 46 insertions(+), 0 deletions(-)
diff --git a/Problems/1345.cpp b/Problems/1345.cpp
@@ -0,0 +1,45 @@
+class Solution {
+public:
+  int minJumps(vector<int> &arr) {
+    if (arr.size() < 2) return 0;
+    if (arr.front() == arr.back()) return 1;
+
+    unordered_map<int, vector<int>> um;
+    unordered_set<int> visited;
+    int n = arr.size();
+
+    for (int i = 0; i < n; i++) um[arr[i]].push_back(i);
+
+    queue<int> q;
+    q.push(0);
+    visited.insert(0);
+    for (int lvl = 0; !q.empty(); lvl++) {
+      for (int k = q.size(); k > 0; k--) {
+        int crnt = q.front();
+        q.pop();
+
+        if (crnt == n - 1) return lvl;
+
+        if (crnt + 1 < n && !visited.count(crnt + 1)) {
+          visited.insert(crnt + 1);
+          q.push(crnt + 1);
+        }
+
+        if (crnt - 1 >= 0 && !visited.count(crnt - 1)) {
+          visited.insert(crnt - 1);
+          q.push(crnt - 1);
+        }
+
+        for (int index : um[arr[crnt]]) {
+          if (!visited.count(index)) {
+            visited.insert(index);
+            q.push(index);
+          }
+        }
+
+        um[arr[crnt]].clear();
+      }
+    }
+    return -1;
+  }
+};
diff --git a/README.md b/README.md
@@ -389,6 +389,7 @@ for solving problems.
 |  1337  |    Easy    | [The K Weakest Rows in a Matrix](Problems/1337.cpp)                                              |
 |  1339  |   Medium   | [Maximum Product of Splitted Binary Tree](Problems/1339.cpp)                                     |
 |  1342  |    Easy    | [Number of Steps to Reduce a Number to Zero](Problems/1342.cpp)                                  |
+|  1345  |    Hard    | [Jump Game IV](Problems/1345.cpp)                                                                |
 |  1346  |    Easy    | [Check if N and Its Double Exist](Problems/1346.cpp)                                             |
 |  1361  |   Medium   | [Validate Binary Tree Nodes](Problems/1361.cpp)                                                  |
 |  1367  |   Medium   | [Linked List in Binary Tree ](Problems/1367.cpp)                                                 |