Nth From The End

September 11, 2018

One solution is to reverse the list, then count from the front:

(define (nth-last n xs)
  (list-ref (reverse xs) (- n 1)))

> (nth-last 3 '(1 2 3 4 5 6 7 8 9))
7

Another solution is to pre-calculate the length of the list, then return the appropriate item counting from the front of the list:

(define (nth-last n xs)
  (list-ref xs (- (length xs) n)))

> (nth-last 3 '(1 2 3 4 5 6 7 8 9))
7

A third solution is to traverse the list keeping two pointers. The first pointer runs through the first n items, then both pointers are incremented simultaneously until the first pointer reaches the end of the list, at which point the second pointer is pointing to the nth-last item:

(define (nth-last n xs)
  (let loop ((n n) (rabbit xs) (greyhound xs))
    (if (positive? n) (loop (- n 1) (cdr rabbit) greyhound)
      (if (pair? rabbit) (loop n (cdr rabbit) (cdr greyhound))
        (car greyhound)))))

> (nth-last 3 '(1 2 3 4 5 6 7 8 9))
7

The greyhound never catches the rabbit.

The first solution allocates space for the reversed list, which you probably don’t want to do. The second solution makes two passes through the list, but the third solution makes only a single pass, so that is probably the one you should prefer.

You can run the program at https://ideone.com/Fm2E9o.

Advertisements

Pages: 1 2

3 Responses to “Nth From The End”

  1. Globules said

    A Haskell version. “Fundamentally different” is in the eye of the beholder…

    import Data.Maybe (listToMaybe)
    import           Data.Vector ((!?))
    import qualified Data.Vector as V
    import Text.Printf (printf)
    
    -- Reverse the list, returning the leading element (if any) after having dropped
    -- the first n-1 elements.
    nthFromEnd1 :: Int -> [a] -> Maybe a
    nthFromEnd1 n xs | n > 0     = listToMaybe . drop (n - 1) . reverse $ xs
                     | otherwise = Nothing
    
    -- Form a list of key/value pairs, returning the element (if any) whose
    -- zero-based key is equal to the length of the list minus n.
    nthFromEnd2 :: Int -> [a] -> Maybe a
    nthFromEnd2 n xs = let len = length xs
                       in lookup (len - n) $ zip [0..] xs
    
    -- Store the list in a vector, returning the element (if any) whose zero-based
    -- position is the length of the vector minus n.
    nthFromEnd3 :: Int -> [a] -> Maybe a
    nthFromEnd3 n xs = let (ys, len) = (V.fromList xs, V.length ys)
                       in ys !? (len - n)
    
    test :: Show a => String -> (Int -> [a] -> Maybe a) -> Int -> [a] -> IO ()
    test desc f n xs = let x = f n xs
                       in printf "%s %2d %s -> %s\n" desc n (show xs) (show x)
    
    main :: IO ()
    main = do
      let xs = [1..9] :: [Int]
    
      test "nthFromEnd1" nthFromEnd1  0 xs
      test "nthFromEnd2" nthFromEnd2  0 xs
      test "nthFromEnd3" nthFromEnd3  0 xs
    
      test "nthFromEnd1" nthFromEnd1  3 xs
      test "nthFromEnd2" nthFromEnd2  3 xs
      test "nthFromEnd3" nthFromEnd3  3 xs
    
      test "nthFromEnd1" nthFromEnd1 13 xs
      test "nthFromEnd2" nthFromEnd2 13 xs
      test "nthFromEnd3" nthFromEnd3 13 xs
    
    $ ./nthfromend
    nthFromEnd1  0 [1,2,3,4,5,6,7,8,9] -> Nothing
    nthFromEnd2  0 [1,2,3,4,5,6,7,8,9] -> Nothing
    nthFromEnd3  0 [1,2,3,4,5,6,7,8,9] -> Nothing
    nthFromEnd1  3 [1,2,3,4,5,6,7,8,9] -> Just 7
    nthFromEnd2  3 [1,2,3,4,5,6,7,8,9] -> Just 7
    nthFromEnd3  3 [1,2,3,4,5,6,7,8,9] -> Just 7
    nthFromEnd1 13 [1,2,3,4,5,6,7,8,9] -> Nothing
    nthFromEnd2 13 [1,2,3,4,5,6,7,8,9] -> Nothing
    nthFromEnd3 13 [1,2,3,4,5,6,7,8,9] -> Nothing
    
  2. Daniel said

    Here’s a solution in C. n is zero-indexed. It doesn’t handle invalid inputs (e.g., setting n=5 for a list with three elements).

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
        int value;
        struct node* next;
    } node_t;
    
    void print_list(node_t* list) {
        printf("{");
        node_t* node = list;
        while (node != NULL) {
            if (node != list) printf("->");
            printf("%d", node->value);
            node = node->next;
        }
        printf("}");
    }
    
    int length(node_t* list) {
        node_t* node = list;
        int len = 0;
        while (node != NULL) {
            ++len;
            node = node->next;
        }
        return len;
    }
    
    void reverse(node_t** list) {
        node_t* prev = NULL;
        node_t* node = NULL;
        node_t* next = *list;
        while (next != NULL) {
            prev = node;
            node = next;
            next = next->next;
            node->next = prev;
        }
        *list = node;
    }
    
    // Get length of list. Then walk the list to the
    // nth element from the end and return.
    int from_end1(node_t* list, int n) {
        int len = length(list);
        node_t* node = list;
        for (int i = 1; i < len - n; ++i) {
            node = node->next;
        }
        return node->value;;
    }
    
    // Reverse the list. Then get the nth element.
    // Reverse the list back to its original ordering
    // and return.
    int from_end2(node_t** list, int n) {
        reverse(list);
        node_t* node = *list;
        for (int i = 0; i < n; ++i) {
            node = node->next;
        }
        reverse(list);
        return node->value;
    }
    
    // Walk n elements into the list. Then walk from there
    // and from the beginning of the list until the first
    // pointer reaches the end.
    int from_end3(node_t* list, int n) {
        node_t* n1 = list;
        node_t* n2 = list;
        for (int i = 0; i < n; ++i) {
            n1 = n1->next;
        }
        while (n1 != NULL && n1->next != NULL) {
            n1 = n1->next;
            n2 = n2->next;
        }
        return n2->value;
    }
    
    int main(int argc, char* argv[]) {
        if (argc < 2) {
            fprintf(stderr, "Usage: %s N [X1 [X2 [X3 ...]]]\n", argv[0]);
            return EXIT_FAILURE;
        }
        int n = atoi(argv[1]);
        node_t* list = NULL;
        for (int i = argc - 1; i >= 2; --i) {
            node_t* node = (node_t*)malloc(sizeof(node_t));
            node->value = atoi(argv[i]);
            node->next = list;
            list = node;
        }
        printf("list:\n  ");
        print_list(list);
        printf("\n");
        int e1 = from_end1(list, n);
        printf("from_end1(list, %d):\n  %d\n", n, e1);
        int e2 = from_end2(&list, n);
        printf("from_end2(list, %d):\n  %d\n", n, e2);
        int e3 = from_end3(list, n);
        printf("from_end3(list, %d):\n  %d\n", n, e3);
        node_t* node = list;
        while (node != NULL) {
            node_t* next = node->next;
            free(node);
            node = next;
        }
        return EXIT_SUCCESS;
    }
    

    Example output:

    $ ./a.out 0 {0..9}
    list:
      {0->1->2->3->4->5->6->7->8->9}
    from_end1(list, 0):
      9
    from_end2(list, 0):
      9
    from_end3(list, 0):
      9
    
    $ ./a.out 3 {0..9}
    list:
      {0->1->2->3->4->5->6->7->8->9}
    from_end1(list, 3):
      6
    from_end2(list, 3):
      6
    from_end3(list, 3):
      6
    
    $ ./a.out 8 {0..9}
    list:
      {0->1->2->3->4->5->6->7->8->9}
    from_end1(list, 8):
      1
    from_end2(list, 8):
      1
    from_end3(list, 8):
      1
    
  3. sri vignesh said

    I know only one.
    b= [10,9,8,7,6,5,4,3,2,1,0]
    index = 7
    print b[len(b) – (index+1)]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: