Verify that each named sequence is strictly increasing

Question

The master launch sequence consists of several independent sequences for different systems. Your goal is to verify that all the individual system sequences are in strictly increasing order. In other words, for any two elements i and j (i < j) of the master launch sequence that belong to the same system (having systemNames[i] = systemNames[j]), their values should be in strictly increasing order (i.e. stepNumbers[i] < stepNumbers[j]).

The input systemNames[i] contains the name of the system to which the ith element of the master launch sequence belongs. Guaranteed constraints:

• 1 ≤ systemNames.length ≤ 5 · 10⁴,
• 1 ≤ systemNames[i].length ≤ 10.

The input stepNumbers[i] is an array of positive integers that contains the value of the ith element of the master launch sequence. Guaranteed constraints:

• stepNumbers.length = systemNames.length,
• 1 ≤ stepNumbers[i] ≤ 10⁹.

Return true if all the individual system sequences are in strictly increasing order, otherwise return false.

Example

For systemNames = ["stage_1", "stage_2", "dragon", "stage_1", "stage_2", "dragon"] and stepNumbers = [1, 10, 11, 2, 12, 111], the output should be launchSequenceChecker(systemNames, stepNumbers) = true.

There are three independent sequences for systems stage_1, stage_2, and dragon. These sequences are [1, 2], [10, 12], and [11, 111], respectively. The elements are in strictly increasing order for all three.

Here is my code.

(defun launchSequenceChecker (systemNames stepNumbers) 
  (setf mmm (remove-duplicates (copy-seq systemNames) :test #'equal))
  (setf lname (map 'list #'identity mmm))
    (setf lnum (make-list  (length mmm):initial-element '0))
  (setf lnum1 (make-list (length mmm):initial-element '1000000001))

    (loop named haha for x from 0 to (1- (length systemNames))
          for name = (aref systemNames x)
          for name1 = (aref systemNames (- (1-(length systemNames)) x))
          for num = (aref stepNumbers x)
          for num1 = (aref stepNumbers (- (1-(length systemNames)) x))
          for pos = (position name lname :test #'equal)
          for pos1 = (position name1 lname :test #'equal)

          if(>= (nth pos lnum) num)
          do(return-from haha nil)
          else
          if(<= (nth pos1 lnum1) num1)
          do(return-from haha nil)
          else
         do
           (setf (nth pos lnum) num )
          (setf (nth pos1 lnum1)num1)
           finally (return-from haha t)))

The problem I am having is that this code passes the tests but exceeds the 6-second time limit.

Answer 1

You are using a list to store the association between names and the previous maximum value. This makes your algorithm O(N^2) because for each element, you might have to go through a list of all previous elements.

You can use a hash table (which has O(1) lookup) to make your algorithm O(N).

You can also add keys when they are not found rather than doing it all at the start for simpler code.

Try to avoid using indices when you can iterate by elements.

quick example solution:

(defun launchSequenceChecker (systemNames stepNumbers)
  (let ((ht (make-hash-table :test 'equal)))
    (loop named l
      for name in systemNames
      for num  in stepNumbers
      do (let ((prev (gethash name ht)))
           (if prev
             (progn
               (when (> prev num)
                 (return-from l nil))
               (setf (gethash name ht)
                     (max prev num)))
             (setf (gethash name ht) num)))
      finally  (return-from l t))))