PROBLEM SOLVING

• restate the problem in own words
• what are the inputs
• what are the outputs
• can outputs be derived fom input
• label important pieces of data
• handle empty, invalid cases
• write out the steps
• solve a problem, if not solve a simple problem

BIG O

how runtime of an algorithm grows when input grows

• constant - O(1)
• O(log n)
• linear - O(n)
• O(nlog n)
• quadratic - O(n^2)

Buit-in methods complexity

OBJECT

• Object.keys(), Object.values(), Object.entries - O(n)
• Object.hasOwnProperty() - O(1)
• Insertion, Removal, Access - O(1)
• Searching - O(n)

ARRAYS

• Insertion, Removal- depends ( end is faster,beginning is slower )
• Access - O(1)
• Searching - O(n)
• push, pop - O(1)
• shift, unshift, concat, slice, splice, sort, forEach, map, filter, reduce - O(n)

TOPICS

1. ARRAYS-&-STRINGS

2. OBJECTS

3. LINKED-LIST

4. STACK & QUEUE

5. TREES

6. GRAPHS

7. RECURSION

8. SORTING

9. SEARCHING

10. DYNAMIC-PROGRAMMING

11. PROBLEM-PATTERNS

SORTING

Default - JS sorting

sorts alphabets

I/p : ['Z', 'D', 'Q', 'I', 'P']
O/p : ['D', 'I', 'P', 'Q', 'Z']

doesnt sort number ( sorted according to Unicode value)

I/p : [55, 8, 92, 11, 5]
O/p : [11, 5, 55, 8, 92]

if a - b = negative value, a comes first,  b comes next
if a - b = positive value, b comes first, then a


arr.sort((a,b) => a-b) // [5, 8, 11, 55, 92]
arr.sort((a,b) => b-a) // [92, 55, 11, 8, 5]

const students = [
  { name: "Alex", grade: 15 },
  { name: "Devlin", grade: 15 },
  { name: "Eagle", grade: 13 },
  { name: "Sam", grade: 14 },
];

students.sort((firstItem, secondItem) => firstItem.grade - secondItem.grade);

Output: 

[
  { name: "Eagle", grade: 13 },
  { name: "Sam", grade: 14 },
  { name: "Alex", grade: 15 }, // original maintained for similar grade (stable sorting)
  { name: "Devlin", grade: 15 }, // original maintained for similar grade (stable sorting)
]; 

Less efficient - Bubble, Insertion, Selection

1. Bubble - largest value bubbles to the top in first iteration ( compare item & swap )

// Optimized BubbleSort with noSwaps
function bubbleSort(arr){
  var noSwaps;
  for(var i = arr.length; i > 0; i--){
    noSwaps = true;
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false;         
      }
    }
    if(noSwaps) break;
  }
  return arr;
}

bubbleSort([8,1,2,3,4,5,6,7]);

2. Insertion- small value in sorted position ( swap smallest element to the beginning )

// Optimized BubbleSort with noSwaps
function bubbleSort(arr){
  var noSwaps;
  for(var i = arr.length; i > 0; i--){
    noSwaps = true;
    for(var j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false;         
      }
    }
    if(noSwaps) break;
  }
  return arr;
}

bubbleSort([8,1,2,3,4,5,6,7]);