Jazzy72
diff --git a/‎leetcode/11. Container With Most Water.md
Lines changed: 19 additions & 1 deletion b/‎leetcode/11. Container With Most Water.md
Lines changed: 19 additions & 1 deletion
diff --git a/‎leetcode/146. LRU Cache.md
Lines changed: 114 additions & 0 deletions b/‎leetcode/146. LRU Cache.md
Lines changed: 114 additions & 0 deletions
diff --git a/‎leetcode/167. Two Sum II - Input array is sorted.md
Lines changed: 18 additions & 1 deletion b/‎leetcode/167. Two Sum II - Input array is sorted.md
Lines changed: 18 additions & 1 deletion
@@ -61,4 +61,22 @@ class Solution {
         return max;
     }
 }
-```
+```
+
+### Third Time
+* Method 1: Two pointer
+  ```Java
+  class Solution {
+      public int maxArea(int[] height) {
+          if(height == null || height.length == 0) return 0;
+          int slow = 0, fast = height.length - 1;
+          int max = 0;
+          while(slow < fast){
+              max = Math.max(max, (fast - slow) * Math.min(height[fast], height[slow]));
+              if(height[fast] < height[slow]) fast--;
+              else slow++;
+          }
+          return max;
+      }
+  }
+  ```
@@ -0,0 +1,114 @@
+## 146. LRU Cache
+
+### Question
+Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
+
+get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
+put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
+
+Follow up:
+* Could you do both operations in O(1) time complexity?
+
+```
+Example:
+
+LRUCache cache = new LRUCache( 2 /* capacity */ );
+
+cache.put(1, 1);
+cache.put(2, 2);
+cache.get(1);       // returns 1
+cache.put(3, 3);    // evicts key 2
+cache.get(2);       // returns -1 (not found)
+cache.put(4, 4);    // evicts key 1
+cache.get(1);       // returns -1 (not found)
+cache.get(3);       // returns 3
+cache.get(4);       // returns 4
+```
+
+### Solution
+* Method 1: HashMap + Bidirectional list
+  ```Java
+  class LRUCache {
+      private int capacity;
+      private Map<Integer, DequeNode> map;
+      private DequeNode dummy;
+      private DequeNode tail;
+      private int size;
+      private static class DequeNode{
+          public int key;
+          public int val;
+          public DequeNode pre, next;
+          public DequeNode(int key, int val){
+              this.key = key;
+              this.val = val;
+          }
+      }
+      public LRUCache(int capacity) {
+          this.capacity = capacity;
+          this.map = new HashMap<>();
+          this.size = 0;
+          this.dummy = new DequeNode(-1, -1);        
+      }
+
+      private void insertHead(DequeNode cur){
+          if(cur.pre != null){
+              cur.pre.next = cur.next;    //remove current node from the list.
+              if(cur.next != null)
+                  cur.next.pre = cur.pre;
+          }
+          DequeNode originalHead = dummy.next;    //insert current node to the head of the list.
+          cur.pre = dummy;
+          dummy.next = cur;
+          cur.next = originalHead;
+          if(originalHead != null){
+              originalHead.pre = cur;
+          }
+      }
+
+      public int get(int key) {
+          if(!map.containsKey(key)) return -1;
+          DequeNode cur = map.get(key);
+          if(cur == tail && size != 1){
+              this.tail = this.tail.pre;
+              this.tail.next = null;
+          }
+          insertHead(cur);
+          return cur.val;
+      }
+
+      public void put(int key, int value) {
+          if(map.containsKey(key)){
+              DequeNode cur = map.get(key);
+              if(cur == tail && size != 1){
+                  tail = cur.pre;
+              }
+              cur.val = value;
+              insertHead(cur);
+          }else{
+              DequeNode node = new DequeNode(key, value);
+              this.map.put(key, node);
+              if(size + 1 <= this.capacity){
+                  if(size + 1 == 1){
+                      this.tail = node;
+                  }
+                  insertHead(node);
+                  size++;
+              }else{
+                  // Need to remove the last node and insert current one.
+                  insertHead(node);
+                  DequeNode originalTail = this.tail;
+                  map.remove(originalTail.key);
+                  this.tail = this.tail.pre;
+                  this.tail.next = null;
+              }
+          }
+      }
+  }
+
+  /**
+   * Your LRUCache object will be instantiated and called as such:
+   * LRUCache obj = new LRUCache(capacity);
+   * int param_1 = obj.get(key);
+   * obj.put(key,value);
+   */
+  ```
@@ -83,4 +83,21 @@ class Solution {
         return new int[]{low + 1, high + 1};
     }
 }
-```
+```
+
+### Third Time
+* Method 1: Two pointer
+  ```Java
+  class Solution {
+    public int[] twoSum(int[] numbers, int target) {
+        int slow = 0, fast = numbers.length - 1;
+        while(slow < fast){
+            int sum = numbers[slow] + numbers[fast];
+            if(sum == target) return new int[]{slow + 1, fast + 1};
+            else if(sum < target) slow++;
+            else fast--;
+        }
+        return new int[]{-1, -1};
+    }
+  }
+  ```