Site Search:
Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts

Java Algorithm

If you want to use algorithm to solve problems instead of doing research on algorithm itself, java probably should be your chosen language. Java collection framework has many data structures and algorithms encapsulated in classes, right there ready for use. Besides, third party java packages such as JGraphT further harnesses the power of algorithm, then handles the control to you in a set of easy to use interfaces. Being a mechanics is cool, being a driver is wise. Be both, my friend.

Understand the idea

Algorithms in a nut shell, boils down to sort and search. You drive down the entropy, then find the information hidden in the mess.

Basic Sorts (javascript)


Selection Sort

Insertion Sort

Shell Sort

Merge Sort

Quick Sort

Priority Queue

Heap Sort

Radex Sort

Sorting algorithms comparison

Basic Search (javascript)



Graph



Java Examples


Union and Find

UnionFindDemo.java improved version

QuickUnion.java

memory usage of java objects

ConvexHull.java

CollisionSystem.java

IntersectionCounter.java

SparseMatrix.java

SparceMatrix.java brutal force version

Hell.java

DFS vs BFS for graph and digraph

BFSWebCrawler.java

Graph.java

Strongly Connected Components in simulated intranet

HelloJGraphT.java


Fitness check

Full understanding of the CS fundamentals such as algorithms, design patterns, data structures, recursions, binary search trees etc. are the keys to solve many different kinds of problems.

We have studied lots of classic data-structures and algorithms so far. Let's pick the most handy and effective ones to practice into instinct.

Algorithms:

Data Structures:


Typical Problems

Linked List

linked list data structure captured the cause-effect relationship between things, it is the building block of many data structures.

reverse linked list

detect loop in linked list

implement Stack

implement Queue

implement HashMap


Binary Search Tree


Besides cause-effect relationship, binary Search Tree introduced branches to capture decision. A parent node points to 2 children nodes. The left child is smaller and the right child is larger. Moving right-ward, the elements are larger, moving leftward the elements are smaller. However, the largest element (right-most) in the left branch is smaller than the smallest element (left-most) in the right branch. Recursive is the state of mind for binary search tree.

traversal a binary search tree


We have studied the traversal sequence of in-order, pre-order and post-order binary tree traversal. In philosophy level. They represent 3 kinds of knowledge for the collection of chaotic nodes.

  1. Seeking for path information at leaf with pre-order traversal -- since the pre-order traversal visits root first, at any node, the traveller has the knowledge of all the nodes from root to the current node, the  path information is completed at leaf node.
  2. Seeking for global information at root with post-order traversal -- since the post-order traversal visits children first, at any node, the traveller has the knowledge of the entire sub-tree of the current node, the global information is completed at root node.
  3. Seeking for trend information at root with in-order traversal -- since the in-order traversal visits left branch first, it will travel to right branch next, at any node, the traveller has the knowledge of the entire left branch and current branch, changes can be easily detected or applied at current node.



Array and String

Indexed array allows random access. The reason for A to B is because you code it that way. Using index as a pointer to the data location, programmer got more flexibility. Details such as iterative, recursive, back-tracing and dynamic programming go a long way in this data structure. String is a char array. String class provided convenient methods such as substring(),  charAt(), startWith(), endWith(), contains(), equal() etc. 

Some small details could save you tons of time because they are used frequently:
  • endIndex = startIndex + length - 1    e.g. "a" 0 = ( 0 + 1 - 1)
  • length = endIndex - startIndex + 1   e.g.  "a" length 1 =  0 - 0 + 1
  • substring(startIndex, endIndex+1)   e.g. "a" substring(0, 1) index 1 is exclusive
  • "a".toCharArray
  • StrinbBuffer's reverse function
  • Character.isDigit
  • startIndex = middleIndex - (length - 1)/2  e.g. "a" 0 = 0 - (1 - 1)/2, "aa" 0 = 0 -  (2 - 1)/2 
  • endIndex = middleIndex + length/2  e.g. "a" 0 = 0 + 1/2, "aa" 1 = 0 + 2/2 

Recursive should not be a stranger to us by now. Merge sort, quick sort, 3-way quick sort, 3-way string quick sort for example, use recursive calls to sort an array. Binary search, for another example, quickly find the rank of an item in an array. Many problems can be solved by applying these algorithms or slightly changing the code in the inner loop.

Besides the above array sorting problem, another typical problems is to find the extreme value among the possible subarray combinations.

Brutal force enumeration of size N arrays generally has big O(N^k), where k is the layer of for loops. Two special enumerations need to emphasis are: 
  1. enumerate all possible subarrays -- O(2^N)
  2. enumerate all possible permutations -- O(N!)
Finding the extreme value can be facilitated by dynamic programming, where we store the middle value, using them to compute the value for later iterations.

There is a cluster of extreme value problems where the global minimum is achieved if local minimum is achieved at each step. Such kind of problem is plenty in natural science, for example, the lowest free energy is achieved for a surface, if and only if each deposited molecular is able to find the lowest energy site to form bond. In CS we use greedy algorithm to solve such kind of problem.

  1. Optimum task distribution for shortest finish time


Even brutal force is not always easy to materialize with code, the most important part of the problem solving is to build the model creatively, which is case by case and won't fit into rigid categorizes.

  1. dictionary words distance

Mathematics and Cleverness

Once we know the basics of programming, the hard part of solving a problem is getting our mind straight instead of writing the code.


find the only repeating element from an array

find the smallest element in a rotating array

find global maximum and minimum
No comments:
Labels: ,

Design Add and Search Words Data Structure

 Problem

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.
 

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
 

Constraints:

1 <= word.length <= 500
word in addWord consists lower-case English letters.
word in search consist of  '.' or lower-case English letters.
At most 50000 calls will be made to addWord and search.

Solution

The fastest word insert and retrieving datastructure we know so far is R-way trie. So lets do it.

import java.util.*;
class Solution {
  public static void main(String...args) {
    WordDictionary wordDictionary = new WordDictionary();
    wordDictionary.addWord("bad");
    wordDictionary.addWord("dad");
    wordDictionary.addWord("mad");
    System.out.println(wordDictionary.search("pad")); // return False
    System.out.println(wordDictionary.search("bad")); // return True
    System.out.println(wordDictionary.search(".ad")); // return True
    System.out.println(wordDictionary.search("b..")); // return True
    System.out.println(wordDictionary.search("c..")); // return False
  }
}

class WordDictionary {
    private static class Node {
      Node[] next = new Node[26];
      boolean isEnd;
    }
  
    Node root;

    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new Node();
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        addNode(root, word, 0);
    }
  
    private void addNode(Node node, String word, int n) {
      if(n == word.length()) 
        return;
      int pos = word.charAt(n) - 'a';
      Node next = node.next[pos];
      if(next == null) {
        next = new Node();
        node.next[pos] = next;
      }
      if(n == word.length() - 1) {
        next.isEnd = true;
      }
      addNode(next, word, n+1);
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
      return search(root, word, 0);
    }
   
    private boolean search(Node node, String word, int n) {
      if(n == word.length())
        return true;
      char c = word.charAt(n);
      if(c == '.') {
        if(n == word.length() - 1) {
          for(Node cur : node.next) {
            if(cur != null && cur.isEnd) {
              return true;
            }
          }
          return false;
        }
        for(Node cur : node.next) {
          if(cur != null && search(cur, word.substring(n+1), 0)) {
            return true;
          }
        }
        return false;
      } else {
        int pos = c - 'a';
        Node next = node.next[pos];
        if(next == null) {
          return false;
        } else {
          if(n == word.length() - 1) {
            return next.isEnd;
          }
          return search(next, word, n+1);
        }
      }
        
    }
}

The time complexity for insert is O(w), where w is the word length. The space complexity for insert is O(w) we need to create w new node.

The time complexity for search hit a normal word is O(w), because we processed each character. The search miss for normal word is O(1) on average. The space complexity for search a normal word is O(w), which proportional to caller stack depth. 

The time complexity for searching a . word is O(wN) where N is the number of keys in the dictionary. In the worst case an all .... search will exam all the possible pass in the dictionary. The space complexity is O(w) which is proportional to caller stack depth.
No comments:
Labels: ,

Implement Trie (Prefix Tree)

 Problem

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true
Note:

You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

Solution

Trie data structure is a multi-node tree. While tree Node as 2 child node, trie node has 26 child node stored in an array. It has an additional boolean field marking the end of a word.



import java.util.*;
class Solution {
  public static void main(String...args) {
    Trie trie = new Trie();
    trie.insert("apple");
    System.out.println(trie.search("apple"));   // returns true
    System.out.println(trie.search("app"));     // returns false
    System.out.println(trie.startsWith("app")); // returns true
    trie.insert("app");   
    System.out.println(trie.search("app"));     // returns true
  }
}

class Trie {
    TrieNode root;
    private static class TrieNode {
      TrieNode[] next = new TrieNode[26];
      boolean isEnd = false;
    }

    /** Initialize your data structure here. */
    public Trie() {
      root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {  //apple
      insert(root, word, 0);
    }
  
    private void insert(TrieNode node, String word, int n) {  //1
      if(n == word.length()) {
        return;
      }
      int p = word.charAt(n) - 'a';
      TrieNode next = node.next[p];
      if(next == null) {
        next = new TrieNode();
        node.next[p] = next;
      }
      if(n == word.length() - 1) {
        next.isEnd = true;
      }
      insert(next, word, n+1);
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
      return search(root, word, 0);
    }
  
    private boolean search(TrieNode node, String word, int n) {
      int p = word.charAt(n) - 'a';
      TrieNode next = node.next[p];
      if(next == null) {
        return false;
      } else {
        if(n == word.length() - 1) {
          return next.isEnd;
        }
        return search(next, word, n+1);
      }
    }
  
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
      return startsWith(root, prefix, 0);
    }
  
    private boolean startsWith(TrieNode node, String word, int n) {
      int p = word.charAt(n) - 'a';
      TrieNode next = node.next[p];
      if(next == null) {
        return false;
      } else {
        if(n == word.length() - 1) {
          return true;
        }
        return startsWith(next, word, n+1);
      }
    }
}

The time complexity is O(w) for all 3 operations, where w is the length of word. We need to process each character in the word of length w.
The space complexity is O(w) for all 3 operations. 
  • For insert, we create w TrieNode, TrieNode has a size 26 array and a boolean field, we assume its size is constant. 
  • For search and startsWith, the recursive call stack is w layer deep, so the space also proportional to O(w).
No comments:
Labels: , , ,

Reorder Data in Log Files

Problem

You have an array of logs.  Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier.  Then, either:

Each word after the identifier will consist only of lowercase letters, or;
Each word after the identifier will consist only of digits.
We will call these two varieties of logs letter-logs and digit-logs.  It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log.  The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties.  The digit-logs should be put in their original order.

Return the final order of the logs.

 

Example 1:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]
 

Constraints:

0 <= logs.length <= 100
3 <= logs[i].length <= 100
logs[i] is guaranteed to have an identifier, and a word after the identifier.

Solution

java Arrays.sort() can take a customized comparator as the second parameter, then use stable sort algorithm merge sort to sort the array in O(M*N*longN) time, the M is the log length and the N is the total number of logs. For the comparator, we need to specify that: for letter logs, we compare content then identifier; for digit log, since merge sort is stable, digit logs are in the original order without us do anything.

We can do the sort faster by group the L letter logs and D digit logs, then sort letter logs only. So the time complexity is O(M*LlogL + D), the M is the cost of compare 2 letter logs lexicographically. LlogL is the cost of sort L letter logs with merge sort. Digit logs don't need to be sorted, so the cost is D. The space complexity is O(M*LogL + M*D) where logL is the space for the tree set and D is the space for the ArrayList.
import java.util.*;
class Solution {
  public static void main(String...args) {
    String[] logs = new String[] {"dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"};
    Set<String> wordLog = new TreeSet<>((o1, o2) -> {
      int idx1 = o1.indexOf(" ");
      int idx2 = o2.indexOf(" ");
      if(o1.substring(idx1 + 1).compareTo(o2.substring(idx2 + 1)) == 0) {
        return o1.substring(0, idx1).compareTo(o2.substring(0, idx2));
      } else {
        return o1.substring(idx1 + 1).compareTo(o2.substring(idx2 + 1));
      }
    });
    List<String> digitLog = new ArrayList<>();
    for(String log : logs) {
      int index = log.indexOf(" ");
      if(Character.isDigit(log.charAt(index+1))) {
        digitLog.add(log);
      } else {
        wordLog.add(log);
      }
    }
    wordLog.stream().forEach(i -> System.out.print(i + ","));
    digitLog.stream().forEach(i -> System.out.print(i + ","));
  }
}

Time complexity O(MLlogL), space complexity O(MLogL + MD)
No comments:
Labels: ,

Longest Increasing Path in a Matrix

 Problem

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution

We can use graph dfs traversal start at each node for find the increasing paths. Since we need to find the max length path, we need to explore all the possibilities. This is a time we think of backtracking. We need to explore all the other directions once we tested one direction. At each node, there will be 3 possible directions that have increasing number, for a m x n matrix, we could end up exploring power(3, mn) states for each node. We can cut down the computation with memorization. We remember the longest increasing path for each node, that way, each node only have to be processes once and the cost reduced to O(mn) for each node. Since there are mn nodes total, the time complexity is O(mmnn), the space complexity is O(mn) for the memorization cache.


import java.util.*;

class Solution {
  int maxLen =  Integer.MIN_VALUE;
  int[][] nums = 
    {
      {9,9,4},
      {6,6,8},
      {2,1,1}
    };
  int[][] memo = new int[nums.length][nums[0].length];
  public static void main(String[] args) {
    
    Solution sol = new Solution();
    sol.solve();
    System.out.println(sol.maxLen);
  }
  private void solve() {
    for(int row = 0; row < nums.length; row++) {
      for(int col = 0; col < nums[0].length; col++) {
        memo[row][col] = dfs(row, col);
        maxLen = Math.max(maxLen, memo[row][col]);
      }
    }
  }
  
  private int dfs(int row, int col) {
    if(memo[row][col] != 0) {
      return memo[row][col];
    }
    
    int[][] directions = new int[][]{
      {0, 1},
      {0, -1},
      {1, 0},
      {-1, 0}
    };
    int tmpMax = 1;
    for(int[] direct: directions) {
      int newRow = row + direct[0];
      int newCol = col + direct[1];
      if(newRow >= 0 && newRow < nums.length && newCol >= 0 && newCol < nums[0].length && nums[row][col] < nums[newRow][newCol]) {
        int len = dfs(newRow, newCol);
        memo[newRow][newCol] = len;
        tmpMax = Math.max(tmpMax, 1 + len);
      }
    }
    return tmpMax;
  }
}
No comments:
Labels: , , ,

Binary Tree Right Side View

 Problem

Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Solution

We can do level traversal the tree and add the last element of a level to the result. For level traversal, we can use a queue to store the elements in the next level, and use the size to remember how many elements to process for the next level.


import java.util.*;

class Solution {
  public static void main(String[] args) {
    Node root = new Node(1, 
                        new Node(2, null, new Node(5, null, null)),
                        new Node(3, null, new Node(4, null, null)));
    List<Integer> result = solve(root);
    result.stream().forEach(System.out::println);
  }

  private static List<Integer> solve(Node root) {
    List<Integer> result = new ArrayList<>();
    if(root == null) return result;
    Queue<Node> queue = new ArrayDeque<>();
    queue.offer(root);
    int size = queue.size();
    while(!queue.isEmpty()) {
      for(int i = 0; i < size; i++) {
        Node cur = queue.poll();
        if(cur.left != null) 
          queue.offer(cur.left);
        if(cur.right != null)
          queue.offer(cur.right);
        if(i == size - 1)
          result.add(cur.val);
      }
      size = queue.size();
    }
    return result;
  }
  static class Node {
    int val;
    Node left;
    Node right;
    public Node(int val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}

The time complexity is O(N) because we need to touch each node, and space complexity is O(N) because the queue in the worst can grow to N/2.


An alternative solution is to use recursive solution with a level marker. The right-most node will equal to the level marker then increase the level marker, so that the other nodes in the same level no longer equal to the level marker so won't be added to the final result.

import java.util.*;

class Solution {
  private List<Integer> result = new ArrayList<>();
  public static void main(String[] args) {
    Node root = new Node(1, 
                        new Node(2, null, new Node(5, null, null)),
                        new Node(3, null, new Node(4, null, null)));
    Solution sol = new Solution();
    int level = 0;
    sol.dfs(root, level);
    sol.result.stream().forEach(System.out::println);
  }

  
  private void dfs(Node root, int level) {
    if(root == null)
      return;
    if(level == result.size()) {
      result.add(root.val);
    }
    if(root.right != null) {
      dfs(root.right, level + 1);
    }
    if(root.left != null) {
      dfs(root.left, level + 1);
    }
  }
  static class Node {
    int val;
    Node left;
    Node right;
    public Node(int val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}

The time complexity is O(N), the space complexity is O(H) which equal to the caller stack size.
No comments:
Labels: ,

Valid Anagram

 Problem


Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Example 2:

Input: s = "rat", t = "car"
Output: false
Note:
You may assume the string contains only lowercase alphabets.

Solution

We can compare the frequency of the characters.


import java.util.*;

class Solution {
  public static void main(String[] args) {
    String s = null, t = "";
    System.out.println(solve(s, t));
  }
  private static boolean solve(String s, String t) {
    if(s == null || t == null)
      throw new IllegalArgumentException("bad input");
    char[] freq = new char[26];
    for(char c : s.toCharArray()) {
      freq[c - 'a']++;
    }
    for(char c : t.toCharArray()) {
      freq[c - 'a']--;
      if(freq[c - 'a'] < 0)
        return false;
    }
    for(int i : freq) {
      if(i != 0)
        return false;
    }
    return true;
  }
}

The time complexity is O(max(L1, L2)), space complexity is O(max(L1, L2)), where L1 and L2 is the length of the two strings.
No comments:
Labels: , ,

Merge k Sorted Lists

Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->1->5,
  2->3->4,
  2->2
]
Output: 1->1->2->3->4->4->5->6

Solution

Brutal force solution will be create a sorted array then create the linked list with the sorted array. Sorting N elements cost O(NlogN) and we need O(N) space for the array. 

The brutal force approach is not optimums because we didn't utilize the feature that the linked lists are already sorted.

We know for sure the minimum element come from the first nodes of the input linked list, so if we add all the k nodes into a priority queue, we can find the minimum node with cost O(klogk). 

  1->     1->5,
  2->     3->4,
  2->     2
Once the minimum node is taken, the next minimum could hid in the rest of the k-1 elements, or it could be the next of the minimum node. So we can replace the minimum node with its next node in the priority queue then continue to find the next minimum node. We can continue to do that until the priority queue is empty.



import java.util.*;

public class Solution {
    public static void main(String args[]) {
      Node head1 = new Node(1, new Node(1, new Node(5, null)));
      Node head2 = new Node(2, new Node(3, new Node(4, null)));
      Node head3 = new Node(2, new Node(2, null));
      //assume Node[] don't have null elements
      Node[] arr = new Node[]{head1, head2, head3};
      Node result = solve(arr);
      printNodes(result);
    }
    private static Node solve(Node[] arr) {
      Node head = null;
      Node tail = null;
      PriorityQueue<ValToLLIndex> pq = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
      for(int i = 0; i < arr.length; i++) {
        pq.add(new ValToLLIndex(arr[i].val, i)); //3-1,5-0,,
        arr[i] = arr[i].next;
      }
      while(!pq.isEmpty()) {
        ValToLLIndex valToLLIndex = pq.poll(); //2-2
        if(head == null) {
          head = new Node(valToLLIndex.val, null);
          tail = head;
        } else {
          tail.next = new Node(valToLLIndex.val, null);
          tail = tail.next;
        }
        int index = valToLLIndex.index;//0
        if(arr[index] != null) {
          pq.add(new ValToLLIndex(arr[index].val, index));
          arr[index] = arr[index].next;
        }
      }
      return head;
    }
  
    static class ValToLLIndex {
      int val;
      int index;
      public ValToLLIndex(int val, int index) {
        this.val = val;
        this.index = index;
      }
        
    }
  
    private static void printNodes(Node head) {
      while(head != null) {
        System.out.print(head.val + "->");
        head = head.next;
      }
      System.out.println("null");
    }
  
    static class Node {
      int val;
      Node next;
      public Node(int val, Node next) {
        this.val = val;
        this.next = next;
      }
    }
}


The time complexity is O(Nklogk) because for each of the N node, we need to add it to the priority queue of size k in order to find the next minimum. The size k priority queue add takes O(klogk), poll takes O(1). 
The space complexity is O(k), which is the size of the priority queue.
No comments:
Labels: , ,

First Unique Character in a String

Problem

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.

Examples:

s = "leetcode"

return 0.

s = "loveleetcode"

return 2.

Note: You may assume the string contains only lowercase English letters.

Solution

We can iterate the string characters, create the frequency map, then we iterate it second time, look up the frequency of each character. The first character with frequency 1 is the answer.

import java.util.*;

class Solution {
  
  public static void main(String[] args) {
    String in = "eebb";
    System.out.println(solve(in));
  }
  private static int solve(String str) {
    //leetcode
    Map<Character, Integer> map = new HashMap<>();
    for(char c : str.toCharArray()) {
      map.put(c, map.getOrDefault(c, 0) + 1);
    }
    //l 1, e 3...
    for(int i = 0; i < str.length(); i++) {
      if(map.get(str.charAt(i)) == 1)
        return i;
    }
    return -1;
  }
}

The time complexity is O(N) and space complexity is O(N).
No comments:
Labels: ,

Valid Parentheses

Problem

Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.


An input string is valid if:


Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.


Example 1:


Input: "()"

Output: true

Example 2:


Input: "()[]{}"

Output: true

Example 3:


Input: "(]"

Output: false

Example 4:


Input: "([)]"

Output: false

Example 5:


Input: "{[]}"

Output: true

Solution

We can use a stack to help matching same type parentheses. When we saw an open brackets, we push that into stack. When we saw a close brackets, we pop an element from the stack. If the top element on the stack matches the type, we continue. If the stack is empty or the element type is not matching, we detected an invalid string.


import java.util.*;

class Solution {
  
  public static void main(String[] args) {
    String str = "([)]";
    System.out.println(valid(str));
  }
  
  private static boolean valid(String str) {
    Stack<Character> stack = new Stack<>();
    for(char c : str.toCharArray()) {
      if(c == '{' || c == '[' || c == '(') {
        stack.push(c); //(
      } else if(c =='}') {
        if(stack.isEmpty()) 
          return false;
        char tmp = stack.pop();
        if(tmp != '{')
          return false;
      } else if(c ==']') {
        if(stack.isEmpty()) 
          return false;
        char tmp = stack.pop();
        if(tmp != '[')
          return false;
      } else if(c ==')') {
        if(stack.isEmpty()) 
          return false;
        char tmp = stack.pop();
        if(tmp != '(')
          return false;
      } else {
        throw new RuntimeException("illegal character");
      }
    }
    if(!stack.isEmpty())
      return false;
    return true;
  }
}

The time complexity is O(N) and the space complexity is O(N)
No comments:
Labels: ,

Two Sum

 Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

[11, 2, 6, 15, -1, 10]

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

We can use one HashMap to store the index of the current value. Later whenever we get a value, we use target - current value as key to lookup the HashMap. If we found it, that is the solution.


import java.util.*;

class Solution {
  
  public static void main(String[] args) {
    int[] arr = new int[]{2, 7, 11, 15};
    int target = 9;
    int[] result = solve(arr, target);
    if(result == null) {
      throw new RuntimeException("impossible");
    }
    System.out.println(result[0] + "," + result[1]);
  }
  //2, 7, 11, 15
  private static int[] solve(int[] arr, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < arr.length; i++) {
      int other = target - arr[i]; //2
      if(map.get(other) != null) {
        return new int[]{map.get(other), i};
      }
      map.put(arr[i], i);  //7 0
    }
    return null;
  }
}

The time complexity is O(N) and space complexity is O(N).
No comments:
Labels: ,

Decode String

Problem

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"
Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Example 4:

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

Solution

This is a recursive solution I brought up in 40 minutes. I believe there are better solutions.


import java.util.*;

class Solution {
  
  public static void main(String[] args) {
    String reg = "abc3[cd]xyz";
    Solution sol = new Solution();
    System.out.println(sol.solve(reg));
  }
  private String solve(String reg) {
    StringBuffer result = new StringBuffer();
    char[] arr = reg.toCharArray();
    for(int i = 0; i < arr.length; i++) {
      char c = arr[i];
      if(c - '0' >= 0 && '9' - c >= 0) {
        int multi = Integer.parseInt(c + "");
        int len = counter(reg.substring(i+1));
        String decoded = decoder(reg.substring(i+1, i + 1 + len));
        StringBuffer sb = new StringBuffer();
        for(int j = 0; j < multi; j++) {
          sb.append(decoded);
        }
        result.append(sb.toString());
        i += len;
      } else if(c == '[' || c == ']') {
        //should never enter here
      } else {
        result.append(c+"");
      }
    }
    return result.toString();
  }
  
  private String decoder(String str) {
    return solve(str.substring(1, str.length()));
  }
  
  private int counter(String str) {
    char[] arr = str.toCharArray();
    int brackets = 0;
    int i = 0;
    for(i = 0; i < arr.length; i++) {
      char c = arr[i];
      if(c == '[') 
        brackets++;
      if(c == ']')
        brackets--;
      if(brackets == 0) 
        break;
    }
    return i + 1;
  }
}

The time complexity and space complexity is hard to estimate. It depends on the decoder string. It is O(length of alphabets in the decoder String + sum of numbers in the decoder String).
The space complexity also depends on the decoder string, in worst case, we have something like the following 1[2[3[4[a]]]], the depth of the caller stack is largest, and we need the most space.
No comments:
Labels:

Add Two Numbers II

Problem

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Solution

One solution is to reverse the 2 linked list, then traversal them and create the result linked list. Finally we reverse the result linked list in order to output the final result.
This approach will have time complexity O(N1 + N2) for we reversed the original linked lists which is N1+N2, then we iterate the linked lists to create the result, the cost is max(N1, N2), then we reverse the result, which cost max(N1, N2). If we reverse the original linked list in place, we don't have to use extra space in this approach. The space complexity is O(1).

For the follow up question, we can not reversing the lists. Then we can convert the two linked lists into two numbers, then we add up the 2 numbers. Finally we convert the sum into a linked list. Please compare with a similar problem reverse an integer for the converting technique used here. 

As a note, if we have to convert linked list into integer and sum them up, we could run into the problem of overflow. If the linked list is long, we need to use java.math.BigInteger instead of simple %, /, *, + operations used here.


class Solution {
  public static void main(String[] args) {
    //(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
    Node head1 = new Node(7, new Node(2, new Node(4, new Node(3, null))));
    Node head2 = new Node(5, new Node(6, new Node(4, null)));
    Node result = solve(head1, head2);
    while(result != null) {
      System.out.print(result.val + "->");
      result = result.next;
    }
    System.out.println("null");
  }
  
  //(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
  private static Node solve(Node head1, Node head2) {
    int a = convertToInt(head1);
    int b = convertToInt(head2);
    int c = a + b; //7243 + 564 = 7807
    return convertToLinkedList(c);
  }
  
  //7 -> 2 -> 4 -> 3
  private static int convertToInt(Node head) {
    int result = 0;   
    while(head != null) {
      result = result * 10 + head.val;
      head = head.next;
    } 
    return result;
  }
  //7807
  private static Node convertToLinkedList(int c) {
    Node pre = null;
    Node cur = null;
    int lsb = 0;
    //7->8->0->7->null
    while(c > 0) {
      pre = cur;
      lsb = c%10; //7
      cur = new Node(lsb, pre);
      c = c/10;
    }
    return cur;
  }
  
  static class Node {
    private int val;
    private Node next;
    public Node(int val, Node next) {
      this.val = val;
      this.next = next;
    }
  }
}

The time complexity is O(N1+N2), the space complexity is O(1).

If we use BigInteger, the time complexity and space complexity depends on the implementation of BigInteger, which could change algorithm according to the size of the number.
No comments:
Labels: ,

LRU Cache

LRU Cache

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.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 );

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

The shortcut is to use LinkedHashMap with capacity 2. We also need to override
removeEldestEntry

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }

The LinkedHashMap implements the eviction with a double linked list. The hashmap maps the key to a double linked list node. Whenever a node is added, it is added after the head node. If the size is bigger 
than capacity, a node is removed from tail. A get operation remove a linked list node, put it at the head. 

import java.util.*;

class Solution {
  public static void main(String[] args) {
    LRUCache cache = new LRUCache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    System.out.println(cache.get(1));       // returns 1
    cache.put(3, 3);    // evicts key 2
    System.out.println(cache.get(2));       // returns -1 (not found)
    cache.put(4, 4);    // evicts key 1
    System.out.println(cache.get(1));       // returns -1 (not found)
    System.out.println(cache.get(3));       // returns 3
    System.out.println(cache.get(4));       // returns 4
  }
  
  static class LRUCache {
    private int capacity = 0;
    private Node head;
    private Node tail;
    private int size;
    private Map<Integer, Node> map = new HashMap<>();
    public LRUCache(int capacity) {
      this.capacity = capacity;
      head = new Node();
      tail = new Node();
      head.next = tail;
      tail.next = head;
    }
    public int get(Integer key) {
      Node node = map.get(key);
      if(node != null) {
        removeNode(node);
        addNode(node);
        return node.val;
      } else {
        return -1;
      }
    }
    
    public void put(Integer key, Integer val) {
      Node node = new Node();
      node.key = key;
      node.val = val;
      addNode(node);
      size++;
      map.put(key, node);
      if(size > capacity) {
        Node tail = removeTail();
        size--;
        map.remove(tail.key);
      }
    }
    
    private void removeNode(Node node) {
      Node pre = node.pre;
      Node next = node.next;
      pre.next = next;
      next.pre = pre;
    }
    
    // head -> node
    // head -> newNode -> node
    private void addNode(Node node) {
      Node next = head.next;
      node.next = next;
      node.pre = head;
      head.next = node;
      next.pre = node;
    }
    
    // noden -> node -> tail
    private Node removeTail() {
      Node node = tail.pre;
      Node pre = node.pre;
      pre.next = tail;
      tail.pre = pre;
      return node;
    }
    
  }
  
  static class Node {
    int key;
    int val;
    Node pre;
    Node next;
  }  
}
All the operations has cost O(1), the space is O(capacity), the extra space came from the double linked list with at most size equal the capacity. 
No comments:
Labels: , ,

Copy List with Random Pointer

Problem:

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val, next, random

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.
 

Example 1:


Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

[7,null] ->[13,0]->[11,4]->[10,2]->[1,0]

Example 2:


Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example 3:



Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.
 

Constraints:

-10000 <= Node.val <= 10000
Node.random is null or pointing to a node in the linked list.
Number of Nodes will not exceed 1000.

Solution:

This is a linked list copy problem with some twist.
In order to copy the linked list, we first clone the head node. Then we clone the head's next node, in order to update the next pointer. After that, we create a while loop, at each step, we move to the next node we just created, then we clone the next node of that node.

With random links, we have 2 difficulties:
1. how to access a random node with cost O(1).
2. how to access a random node that we haven't created yet.

For the difficulty 1, we can create a HashMap that maps from the old linked-list node to the new linked-list node. Therefore, with the random link in the old linked list node, we can find the random node, then use the random node to lookup the Hashmap in order to find the node we have cloned.

For the difficulty 2, we can create a the random node first before we create the next node.

import java.util.*;


class Solution {
  Map<Node, Node> map = new HashMap<>();
  public static void main(String[] args) {
    //[7,null] ->[13,0]->[11,4]->[10,2]->[1,0]
    Solution sol = new Solution();
    Node head = sol.createRandomLL();
    sol.print(head);
    Node copy = sol.deepCopy(head);
    sol.print(copy);
    //print
  }
  
  private void print(Node head) {
    while(head!=null) {
      System.out.print("[" + head.val + ", ");
      if(head.rand == null) 
        System.out.print("null] ->");
      else
        System.out.print(head.rand.val + "]->");
      head = head.next;
    }
    System.out.println("null");
  }
  
  private Node createRandomLL() {
    Map<Integer, Node> tmp = new HashMap<>();
    int[] vals = new int[]{7, 13, 11, 10, 1};
    Integer[] rands = new Integer[]{null, 0, 4, 2, 0};
    for(int i = 0; i < vals.length; i++) {
      tmp.put(i, new Node(vals[i], null, null));
    }
    for(int i = 0; i < vals.length; i++) {
      Node curr = tmp.get(i);
      curr.next = tmp.getOrDefault(i+1, null);
      curr.rand = tmp.get(rands[i]);
    }
    return tmp.get(0);
  }
  
  private Node deepCopy(Node head) {
    if(head != null) {
      Node old = head;
      Node newNode = copyNode(old);
      while(old != null) {
        newNode.next = copyNode(old.next);
        newNode.rand = copyNode(old.rand);
        old = old.next;
        newNode = newNode.next;
      }
      return map.get(head);
    }
    return null;
  }
  
  private Node copyNode(Node head) {
    if(head == null)
      return null;
    Node newNode = map.getOrDefault(head, new Node(head.val, null, null));
    map.put(head, newNode);
    return newNode;
  }
  class Node {
    int val;
    Node next;
    Node rand;
    public Node(int val, Node next, Node rand) {
      this.val = val;
      this.next = next;
      this.rand = rand;
    }
  }
  
}

The time complexity is O(N) because we need to iterate the linked list once. The space complexity is O(N) due to the extra space the HashMap occupies.

No comments:
Labels: ,

Longest Turbulent Subarray

Problem:

A subarray A[i], A[i+1], ..., A[j] of A is said to be turbulent if and only if:

For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.
That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Example 1:

Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])
Example 2:

Input: [4,8,12,16]
Output: 2
Example 3:

Input: [100]
Output: 1

Note:

1 <= A.length <= 40000
0 <= A[i] <= 10^9

Solution:

We can use a pointer mark the start position of a turbulent subarray, then move the tail of turbulent subarray one step at a time. At each step, we compare the current value with previous and next value to check if we can move the tail one step further. If we can not move the tail further, the current position is the end of a turbulent subarray and the start of the next turbulent subarray. So calculate the length of the previous turbulent subarray, then we move the starting point here to mark the beginning of the next turbulent subarray. The problem's difficulty is in the details of no changing sequence, we need to consider the special case of 1, 1, 1, 1, 1, 1, 1, 1. The solution should return 1 instead of 2.

class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{3};
    System.out.println(solve(arr));
  }
  private static int solve(int[] arr) {
    int start = 0;
    int result = 1;  //2
    if(arr.length ==  1) return 1;
    //8 8 8 8 8 8 8 8
    for(int i = 1; i < arr.length; i++) { //9,4,2,10,7,8,8,1,9
      if(i == arr.length - 1 || (Integer.compare(arr[i], arr[i-1]) * Integer.compare(arr[i+1], arr[i]) >= 0)) {
        if((arr[i] - arr[i-1]) != 0) {
          result = Math.max(result, i - start + 1);
        }
        start = i;
      }
    }
    return result;
  }
}


The time complexity is O(N) because we iterate the array only once, the space complexity is O(1).


No comments:
Labels: ,

Letter Case Permutation

Problem:

Letter Case Permutation
Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.  Return a list of all possible strings we could create.

Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]
Note:

S will be a string with length between 1 and 12.
S will consist only of letters or digits.

Solution:

This problem can be solved with traceback.
We use a stringbuffer to store the result string, use an integer to store the current character we are processing. For a position, we can have digit or letter. For digit, we don't have choice but add it to the result stringbuffer. For letter, we can choose to store an Upper case or Lower case letter. So whenever we meet a letter, there is a 2 branch choices. Finally, when the stringbuffer size is equal to the original string size, we add the content to the final result set, then we remove the character we added in the previous step, give the other option a try if there is any. 

         a        A
         1        1
       b    B   b    B
       2    2   2    2

import java.util.*;
class Solution {
  Set<String> result = new HashSet<>();
  public static void main(String...args) {
    Solution sol = new Solution();
    sol.solve("a1b2", new StringBuffer(), 0);
    for(String s : sol.result)
      System.out.println(s);
  }
  private void solve(String in,StringBuffer sb, int pos) {
    if(pos >= in.length()) {
      result.add(sb.toString());
      return;
    }
    char c = in.charAt(pos);
    if(Character.isDigit(c)) {
      sb.append(c);
      solve(in, sb, pos+1);
      sb.deleteCharAt(sb.length() - 1);
    } else {
      sb.append(c);
      solve(in, sb, pos+1);
      sb.deleteCharAt(sb.length() - 1);
      sb.append(duel(c));
      solve(in, sb, pos+1);
      sb.deleteCharAt(sb.length() - 1);
    }
  }
  private char duel(char c) {
    if(Character.isUpperCase(c))
      return Character.toLowerCase(c);
    else
      return Character.toUpperCase(c);
  }
}


If there are L letters in the string, we need to deal with 2^L possible states, the time complexity is O(2^L), we only used a stringbuffer to store the temp result, the space complexity is O(string.length()).


No comments:
Labels: ,

Peak Index in a Mountain Array

Problem:

Peak Index in a Mountain Array
Let's call an array A a mountain if the following properties hold:

A.length >= 3
There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

Input: [0,1,0]
Output: 1
Example 2:

Input: [0,2,1,0]
Output: 1
Note:

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A is a mountain, as defined above.

Solution:

We can use binary search to find the peak. 

class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{0,2,1,0};
    int r = solve(arr);
    System.out.println(r);
  }
  private static int solve(int[] arr) { //1 2 3 4 5 7 3
    int lo = 0;   //4
    int hi = arr.length - 1;    //6
    while(lo < hi) {
      int mid = lo + (hi - lo)/2;    //5
      if(arr[mid-1] < arr[mid] && arr[mid] < arr[mid+1]) {
        lo = mid + 1;
      } else if (arr[mid-1] > arr[mid] && arr[mid] > arr[mid+1]) {
        hi = mid;
      } else {
        return mid;
      }
    }
    return lo;
  }
}

The time complexity is O(logN) and the space complexity is O(1).

No comments:
Labels: ,

Delete Columns to Make Sorted

Problem:

Delete Columns to Make Sorted
We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef", "vyz"], and the remaining columns of A are ["b","v"], ["e","y"], and ["f","z"].  (Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]]).

Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.

Return the minimum possible value of D.length.



Example 1:

Input: A = ["cba","daf","ghi"]
Output: 1
Explanation:
After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order.
If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.
Example 2:

Input: A = ["a","b"]
Output: 0
Explanation: D = {}
Example 3:

Input: A = ["zyx","wvu","tsr"]
Output: 3
Explanation: D = {0, 1, 2}


Constraints:

1 <= A.length <= 100
1 <= A[i].length <= 1000

Solution:

This problem has a long description, but boiling down to remove the columns with decreasing order. 

class Solution {
  public static void main(String...args) {
    String[] arr = new String[]{"cba","daf","ghi"};
    int result = solve(arr);
    System.out.println(result);
  }
  private static int solve(String[] arr) {
    int counter = 0;
    for(int i = 0; i < arr[0].length(); i++) {
      for(int j = 0; j < arr.length - 1; j++) {
        if(arr[j].charAt(i) > arr[j+1].charAt(i)) {
          counter++;
          break;
        }
      }
    }
    return counter;
  }
}

The time complexity is O(A) which is the length of the string multiply the total number of strings, the space cost is O(1).
No comments:
Labels: ,

N-Repeated Element in Size 2N Array

Problem:

N-Repeated Element in Size 2N Array
In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

Input: [1,2,3,3]
Output: 3
Example 2:

Input: [2,1,2,5,3,2]
Output: 2
Example 3:

Input: [5,1,5,2,5,3,5,4]
Output: 5

Note:

4 <= A.length <= 10000
0 <= A[i] < 10000
A.length is even

Solution:

We can iterate the array, count each element. The counting can be stored in HashMap datastructure, so that put and get cost O(1). 

import java.util.*;
class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{2,1,2,5,3,2};
    int result = solve(arr);
    System.out.println(result);
  }
  private static int solve(int[] arr) {
    Map<Integer, Integer> map = new HashMap<>();
    for(int i : arr) {
      map.put(i, map.getOrDefault(i, 0) + 1);
    }
    for(Integer i : map.keySet()) {
      if(map.get(i) == arr.length/2)
        return i;
    }
    return Integer.MIN_VALUE;
  }
}


Since we need to iterate the array once and iterate the HashMap once, the time complexity is O(N), the space complexity is O(N) due to the extra space for the HashMap.


No comments:
Labels: ,
Subscribe to: Posts (Atom)