## Nth From The End

### September 11, 2018

Counting from the end of the list, the third-last item in the list (1 2 3 4 5 6 7 8 9) is 7.

Your task is to write a program to find the nth-last item in a list; you must provide at least three fundamentally different solutions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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);
return EXIT_FAILURE;
}
int n = atoi(argv);
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)]