Friedrich Ewald My Personal Website

Posts


  • Leetcode: Remove nth node from end of list

    Given the head of a linked list, remove the nth element from the end of the list and return the head of the list. As a follow-up, this should be done with one iteration. The most obvious solution is to count the number of elements in the list in one iteration. This is necessary, because we don’t know initially how long the list is. Then iterate over the list again and once the index is reached, set pointer = pointer.next. This way the nth element is skipped. However, there is a more elegant way to achieve this.

    Continue reading

  • Leetcode: Sort colors

    Given an array nums with n colored objects, sort the array in place so that the colors are orders. The colors are represented by the numbers 0, 1, and 2. The easiest way to achieve this is via quicksort in O(n*log n).

    Continue reading

  • Leetcode: Find first and last position of element in sorted arrays

    Given a list of ascending sorted numbers, find the first and last occurrence of a target number. For example for the list [1,2,2,3,4] and target = 2, the result would be [1,2]. If the target number is not in the array, return [-1,-1].

    Continue reading

  • Leetcode: Three sum

    Given a list of integers, add three integers at the same time so that the sum of those integers is 0. There should be no repetition of integers, for example [-1, 0, 1] is equivalent to [-1, 1, 0].

    Continue reading

  • Leetcode: Longest Consecutive Sequence

    From an unsorted array nums, return the length of the longest consecutive sequence of numbers as an integer. For example, the list [100, 4, 200, 1, 3, 2] would return 4, because the longest consecutive sequence is [1, 2, 3, 4] with a length of 4. The algorithm should perform in O(n). Not mentioned in the task is that there can be duplicates of numbers. They should be ignored. The main problem when developing this algorithm is for it to perform it in O(n). A brute force method is quite easy and works for smaller lists. The pseudo code looks like this:

    for every element in list
      while next element in list
        take next element
        increment counter by 1
      endwhile
      return longest counter
    endfor
    This approach works but is very time consuming with a complexity of O(n^2). This is because for every element in the list we need to possibly visit every other element in the list.

    Continue reading

Page: 9 of 28