add 1409

fishercoder1534 · fishercoder1534 · commit c8bd6147c95f · 2020-04-12T07:31:09.000-07:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1409|[Queries on a Permutation With Key](https://leetcode.com/problems/queries-on-a-permutation-with-key/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1409.java) | |Medium|Array|
 |1408|[String Matching in an Array](https://leetcode.com/problems/string-matching-in-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1408.java) | |Easy|String|
 |1403|[Minimum Subsequence in Non-Increasing Order](https://leetcode.com/problems/minimum-subsequence-in-non-increasing-order/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1403.java) | |Easy|Greedy, Sort|
 |1401|[Circle and Rectangle Overlapping](https://leetcode.com/problems/circle-and-rectangle-overlapping/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1401.java) | |Medium|Geometry|
diff --git a/src/main/java/com/fishercoder/solutions/_1409.java b/src/main/java/com/fishercoder/solutions/_1409.java
@@ -0,0 +1,67 @@
+package com.fishercoder.solutions;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * 1409. Queries on a Permutation With Key
+ *
+ * Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:
+ * In the beginning, you have the permutation P=[1,2,3,...,m].
+ * For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P.
+ * Notice that the position of queries[i] in P is the result for queries[i].
+ * Return an array containing the result for the given queries.
+ *
+ * Example 1:
+ * Input: queries = [3,1,2,1], m = 5
+ * Output: [2,1,2,1]
+ * Explanation: The queries are processed as follow:
+ * For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5].
+ * For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5].
+ * For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5].
+ * For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5].
+ * Therefore, the array containing the result is [2,1,2,1].
+ *
+ * Example 2:
+ * Input: queries = [4,1,2,2], m = 4
+ * Output: [3,1,2,0]
+ *
+ * Example 3:
+ * Input: queries = [7,5,5,8,3], m = 8
+ * Output: [6,5,0,7,5]
+ *
+ * Constraints:
+ * 1 <= m <= 10^3
+ * 1 <= queries.length <= m
+ * 1 <= queries[i] <= m
+ * */
+public class _1409 {
+    public static class Solution1 {
+        public int[] processQueries(int[] queries, int m) {
+            Map<Integer, Integer> indexToValMap = new HashMap<>();
+            for (int i = 1; i <= m; i++) {
+                indexToValMap.put(i - 1, i);
+            }
+            int[] result = new int[queries.length];
+            for (int i = 0; i < queries.length; i++) {
+                int val = queries[i];
+                int pos = findPos(indexToValMap, val);
+                result[i] = pos;
+                for (int j = pos; j > 0; j--) {
+                    indexToValMap.put(j, indexToValMap.get(j - 1));
+                }
+                indexToValMap.put(0, val);
+            }
+            return result;
+        }
+
+        private int findPos(Map<Integer, Integer> map, int val) {
+            for (int pos : map.keySet()) {
+                if (map.get(pos) == val) {
+                    return pos;
+                }
+            }
+            return -1;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1409Test.java b/src/test/java/com/fishercoder/_1409Test.java
@@ -0,0 +1,24 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1409;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertArrayEquals;
+
+public class _1409Test {
+    private static _1409.Solution1 solution1;
+    private static int[] queries;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1409.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        queries = new int[]{3, 1, 2, 1};
+        assertArrayEquals(new int[]{2, 1, 2, 1}, solution1.processQueries(queries, 5));
+    }
+
+}
