Home | Projects | Notes > Problem Solving > Lessons Learned

Lessons Learned

• [LC-263. Longest Common Prefix] [] operator and at() of the vector container:

  For the operator [], the position after the last character is valid index. It will return the value that is generated by the default constructor of the character type which is ‘\0’.

  However, for at(), the position after the last character is NOT valid. It will throw an out_of_range exception when it reaches that position.

  xxxxxxxxxx
  5
  1
  strs[0].at(i);    // throws an exception when i hits the position after the last 
  2
                    // character
  3
  
  4
  strs[0][i];       // returns '\0' when i reaches the position after the last
  5
                    // character
  

• [LC-263. Ugly Number] The time complexity of dividing an integer $n$$n$ with a specific number repeatedly until the quotient becomes 0 is $O(\log n)$$O(\log n)$.

• [LC-94. Binary Tree Inorder Traversal] Use helper function if necessary.

• The space needed to read in or return an instance is not included in the space complexity analysis of an algorithm; otherwise, every algorithm would have O(n) space complexity.

• [LC-2. Add Two Numbers] When adding two one-digit numbers:

  • Sum without carry: sum % 10

  • Carry: sum / 10

• [LC-1122. Relative Sort Array] Using map to keep track of elements and their occurences in an array:

  xxxxxxxxxx
  23
  1
  vector<int> v = {1, 3, 4, 2, 4, 2, 4, 4};
  2
  
  3
  // insert elements into the map 
  4
  // - key  : elements of arr1
  5
  // - value: number of occurrences
  6
  map<int, int> m;
  7
  for (auto n : v)
  8
  {
  9
      m[n]++;   // if the passed key does not exist in the map, a new element gets
  10
                // inserted into the map automatically (the value of the new element is
  11
                // initialized by the default constructor of its type; in this case '0')
  12
  }
  13
  // now map stores {1, 1}, {2, 2}, {3, 1}, {4, 4}.
  14
  
  15
  // print the elements in an ascending order
  16
  for (auto n : m)
  17
  {
  18
      while (n.second > 0)
  19
      {
  20
          cout << n.first << endl;
  21
          n.second--;
  22
      }
  23
  }
  

  Erasing a map element:

  xxxxxxxxxx
  3
  1
  map<int, int> m;
  2
  ...
  3
  m.erase(key);
  

• If a multiset contains duplicates, you can't erase() to remove only the first element of these duplicates. (erase(value) will erase all ocurrences of value in the multiset.) Instead, you can code as follows:

  xxxxxxxxxx
  9
  1
  std::multiset<Elem> coll;
  2
  ...
  3
  // remove first element with passed value
  4
  std::multiset<Elem>::iterator pos;    // or you could simply:
  5
  pos = coll.find(value);               // auto pos = coll.find(value);
  6
  if (pos != coll.end())
  7
  {
  8
      coll.erase(pos);
  9
  }
  

• Insert operations of vectors

  xxxxxxxxxx
  5
  1
  c.push_back(elem);
  2
  c.insert(pos, elem);
  3
  c.insert(pos, n, elem);
  4
  c.insert(pos, beg, end);
  5
  c.insert(pos, initlist);
  

  Be careful about the following situation:

  xxxxxxxxxx
  5
  1
  vector<int> v;
  2
  
  3
  // insert '1' at the beginning of the vector
  4
  v.insert(0, 1);           // illegal! 
  5
  v.insert(c.begin(), 1);   // OK!
  

• [EPI-5.1. Computing the Parity of a Word] Tips on Bit Manipulation

  • Clear the lowest set bit in $x$$x$

    • x & (x - 1)

  • Extract the lowest set bit of $x$$x$

    • x & ~(x - 1)

  [!] Application: [LC-191-Number-of-1-Bits]

• [LC-88. Merge Sorted Array] Using post-increment/decrement operators to advance indexes:

  xxxxxxxxxx
  1
  1
  a[i++] = b[j++];
  

  instead of

  xxxxxxxxxx
  3
  1
  a[i] = b[j];
  2
  i++;
  3
  j++;
  

• [LC-100. Same Tree] Space complexity of recursion: Space complexity of recursion is always the height (or depth) of recursion. General rule of thumb is that there can be at most $h$$h$ height in a tree traversal where $h$$h$ is the legth of deepest node from the root.

  Space complexity of recursion $=O(\text{depth of recursion tree})$$=O(\text{depth of recursion tree})$

• C++ bit shift operators (>> or <<) does NOT shift "in place".

  xxxxxxxxxx
  6
  1
  int n = 4;    // (0100)
  2
  
  3
  n >> 1;       // returned value will be lost and 'n' will remain as 4
  4
  
  5
  n >>= 1;      // n = 2 (0010)
  6
  n <<= 1;      // n = 4 (0100)
  

• [LC-160. Intersection of Two Linked Lists] Idiom for searching in (multi)maps, (multi)sets, unordered containers.

  xxxxxxxxxx
  4
  1
  if (c.find(key) != c.end())
  2
  {
  3
      // key is found, do someting!
  4
  }
  

• [LC-118. Pascal's Triangle] Inserting an individual element into a 2D vector:

  xxxxxxxxxx
  6
  1
  vector<vector<int>> v;
  2
  v[0].push_back(1);                // ERROR since v[0] does not exist yet!
  3
  v[0].push_back(vector<int>(5, 1); // OK (inserts {1, 1, 1, 1, 1} into v[0])
  4
  
  5
  vector<vector<int>> v(3);         // creates a 2D vector that contains 3 vectors
  6
  v[0].push_back(1);                // OK (inserts '1' at the end of the vector v[0])
  

  When first inserting an element into a 1D vector of a 2D vector, make sure that 1D vector already exists.

• [LC-169. Majority Element] Sometimes using the dummy return value can be useful:
  For example,

  xxxxxxxxxx
  13
  1
  int majorityElement(vector<int>& nums) 
  2
  {
  3
      map<int, int> m;
  4
      int ret;
  5
  
  6
      for (auto n : nums)
  7
      {
  8
          if (++m[n] > n/2)
  9
              ret = n;
  10
      }
  11
  
  12
      return ret;
  13
  }
  

  Above code can be rewritten as follows using the dummy return variable:

  xxxxxxxxxx
  15
  1
  int majorityElement(vector<int>& nums) 
  2
  {
  3
      map<int, int> m;
  4
  
  5
      for (auto n : nums)
  6
      {
  7
          if (++m[n] > n/2)
  8
              return n;
  9
      }
  10
  
  11
      // dummy return value (program will never reach this point since 
  12
      // - 'nums' has at least one element
  13
      // - the 'majority element' always exists in 'nums'
  14
      return -1;
  15
  }
  

  This can be useful when all the possible return case exists in the loop.

  [!] Note: Notice how you can insert elements into the map and increase their counters.

   

• [LC-202. Happy Number] Idiom for summing up each digit of a number n:

  xxxxxxxxxx
  7
  1
  int sum = 0;
  2
  
  3
  while (n > 0)
  4
  {
  5
      sum += n % 10;
  6
      n /= 10;
  7
  }
  

  At the termination of this while loop, sum will contain the sum of each digit of the number n.

• [LC-225. Implement Stack Using Queues] pop operation of the C++ STL Queue container does NOT return the value. To do something with the popped value, top operation has to be used first to store the value to be popped.

  The core interface of the C++ STL Queue:

  xxxxxxxxxx
  10
  1
  Interface         Effect
  2
  ================  ======================================================================
  3
  push()            Inserts an element into the queue
  4
  front()           Returns the next element in the queue without removing it (the element
  5
                    that was inserted first)
  6
  back()            Returns the last element in the queue without removing it (the element
  7
                    that was inserted last)
  8
  pop()             Removes an element from the queue (does not return it)
  9
  size()            Returns the current number of elements
  10
  empty()           Returns whether the queue is empty (equivalent to size()==0)
  

• To flip all the bits of a binary number, XOR the number with the sequence of 1s of the same length. XOR is simply an addition of binary digits without carry.

  xxxxxxxxxx
  4
  1
  int n = 6;    // 0110(2)
  2
  n ^= 15;      // now n contains 9 which is 1001(2)
  3
  // or
  4
  n ^= 0xF;
  

• [LC-205. Isomorphic Strings] Declaring vector with initial size and values:

  xxxxxxxxxx
  1
  1
  vector<int> v(256, -1);   // reserve 256 elements initialized to '-1'
  

• Don't be confused about the iterator used in a for loop. Following is a silly mistake I made under the stressful condition that wasted much of my time.

  xxxxxxxxxx
  5
  1
  for (auto pos = c.begin(); pos < c.end(); ++pos) { }    // WRONG!
  2
  //                             ^
  3
  
  4
  for (auto pos = c.begin(); pos != c.end(); ++pos) { }   // OK!
  5
  //                             ^
  

  < or > are NOT overloaded for iterators.

• Iterate over the elements of a map<char, int> using the range-based for loop:

  xxxxxxxxxx
  8
  1
  map<char, int> m;
  2
  
  3
  for (auto elem : m)   // here the type of 'elem' is pair<char, int>
  4
      cout << m.first << ", " << m.second << endl;
  5
  
  6
  // following will not work!
  7
  for (char elem : m)   // elem's type mis-match
  8
      ...
  

• Using substr() to tokenize a string that contains space delmited words:

  xxxxxxxxxx
  6
  1
  string name = "";
  2
  string year = "";
  3
  string s = "KyungjaeLee 1988"
  4
  
  5
  name = s.substr(0, s.find(' '));  // name contains "KyungjaeLee"
  6
  year = s.substr(s.find(' ') + 1); // name contains "1988"
  

• c.clear() empties the container where c can be vector, set, multiset, map,multimap, or any unordered containers.

• erase() allows differnt parameter sets. Be sure to understand their usages.

  Vector:

  xxxxxxxxxx
  6
  1
  Operation                 Effect
  2
  ========================  ==============================================================
  3
  c.erase(pos)              Removes the element at iterator position pos and returns the
  4
                            position of the next element
  5
  c.erase(beg, end)         Removes elements of the range [beg, end) and returns the
  6
                            position of the next element
  

  Set/Multiset, Map/Multimap, Unordered Containers:

  xxxxxxxxxx
  8
  1
  Operation                 Effect
  2
  ========================  ==============================================================
  3
  c.erase(val)              Removes all elements equal to val and returns the number of
  4
                            removed elements
  5
  c.erase(pos)              Removes the element at iterator position pos and returns the
  6
                            following position (returned nothing before C++11)
  7
  c.erase(beg, end)         Removes all elements of the range [beg, end) and returns the
  8
                            following position (returned nothing before C++11)
  

• [LC-228. Summary Ranges] Consecutive string concatenation

  xxxxxxxxxx
  3
  1
  string s1 = "abc";
  2
  string s2 = "ghi";
  3
  string s3 = s1 + "def" + s2;  // s3 will be "abcdefghi"