CareerCup

{{
public class IndexofLastDuplicate {

public static void main(String[] args) {
int arr[] = { 1, 2, 5, 6, 6, 7, 9, 9, 9, 9, 9, 9 };
int lastIndex = findLastDuplicateIndex(arr);
System.out.println("Last duplicate" + lastIndex);
}

public static int findLastDuplicateIndex(int[] arr) {
int lastIndex = -1;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
lastIndex = i + 1;
}
}
return lastIndex;
}

}
}}

static int lastIndex(int[] arr)  {
        if (arr == null || arr.length <= 1) return -1;
        int len = arr.length;
        for (int i = len-1; i >0; i--) {
            if (arr[i] == arr[i-1]) return i;
        }
        return -1;
    }

public static int findLastIndexOfDuplicateNumber(int[] arr) {
		int len = arr.length - 1;
		for (int i = len; i >= 0; i--) {
			int j = i - 1;
			if (j >= 0 && arr[i] == arr[j]) {
				return i;
			} else {
				continue;
			}

		}
		return -1;

	}

public static int lastIndexDuplicateNumber(int[] input) {
        if (input == null) {
            return -1;
        }
        int prev = input[0];
        int lastIndex = -1;
        for (int i = 1; i < input.length; i++) {
            int num = input[i];
            if (prev == num) {
                //duplicate number
                lastIndex = i;
            }
            prev = num;
        }
        return lastIndex;
    }

#include <stdio.h>

void DupLastIndex (int *arr, int n) {
  int i;
  
  if (arr == NULL || n <= 0) {
    return;
  }
  
  for (i = n - 1; i > 0; i--) {
    if (arr[i] == arr[i - 1]) {
      printf("Last index: %d\nLast duplicate item: %d\n", i, arr[i]);
      return;
    }
  }
}

int main() {
  int arr[] = {1, 2, 5, 6, 6, 7, 9};
  
  DupLastIndex (arr, sizeof(arr)/sizeof(int));
  
  return 0;
}

- Walk the array from right to left.
- Compare i-th item with (i - 1)th item.
- If there's a match, print i. You are done.

#include <stdio.h>

void DupLastIndex (int *arr, int n) {
  int i;
  
  if (arr == NULL || n <= 0) {
    return;
  }
  
  for (i = n - 1; i > 0; i--) {
    if (arr[i] == arr[i - 1]) {
      printf("Last index: %d\nLast duplicate item: %d\n", i, arr[i]);
      return;
    }
  }
}

int main() {
  int arr[] = {1, 2, 5, 6, 6, 7, 9};
  
  DupLastIndex (arr, sizeof(arr)/sizeof(int));
  
  return 0;
}

- Walk the array from right to left.
- Compare i-th item with (i - 1)th item.
- If there's a match, print i. You are done.

#include <stdio.h>

void DupLastIndex (int *arr, int n) {
  int i;
  
  if (arr == NULL || n <= 0) {
    return;
  }
  
  for (i = n - 1; i > 0; i--) {
    if (arr[i] == arr[i - 1]) {
      printf("Last index: %d\nLast duplicate item: %d\n", i, arr[i]);
      return;
    }
  }
}

int main() {
  int arr[] = {1, 2, 5, 6, 6, 7, 9};
  
  DupLastIndex (arr, sizeof(arr)/sizeof(int));
  
  return 0;
}

- Walk the array from right to left.
- Compare i-th item with (i - 1)th item.
- If there's a match, print i. You are done.

#include <stdio.h>

void DupLastIndex (int *arr, int n) {
  int i;
  
  if (arr == NULL || n <= 0) {
    return;
  }
  
  for (i = n - 1; i > 0; i--) {
    if (arr[i] == arr[i - 1]) {
      printf("Last index: %d\nLast duplicate item: %d\n", i, arr[i]);
      return;
    }
  }
}

int main() {
  int arr[] = {1, 2, 5, 6, 6, 7, 9};
  
  DupLastIndex (arr, sizeof(arr)/sizeof(int));
  
  return 0;
}

O(nlogn) using binary search

#include <iostream>
using namespace std;

int FindIndex(int* array, int mid)
{
	if(array[mid-1] == array[mid] && array[mid] == array[mid+1])
	{
		return mid+1;
	}
	else if(array[mid-1] == array[mid])
	{
		return mid;
	}
	else if(array[mid] == array[mid+1])
	{
		return mid+1;
	}
	else
	{
		return -1;
	}
}

int FindLastIndexOfDuplicate2(int* array, int start, int end)
{
	if(start == end)
	{
		return -1;
	}
	if(start+1 == end)
	{
		return (array[start] == array[end] ? end : -1);
	}
	else if(start+2 == end)
	{
		return FindIndex(array, start+1);
	}
	else if(start+3 == end)
	{
		int x = FindIndex(array, start+2);
		return x == -1 ? FindIndex(array, start+1) : x;
	}
	int mid = (end-start)/2 + start;
	if(array[mid-1] == array[mid] && array[mid] == array[mid+1])
	{
		return FindLastIndexOfDuplicate2(array, mid, end);
	}
	else if(array[mid-1] == array[mid])
	{
		return FindLastIndexOfDuplicate2(array, mid-1, end);
	}
	else if(array[mid] == array[mid+1])
	{
		return FindLastIndexOfDuplicate2(array, mid, end);
	}
	else
	{
		return FindLastIndexOfDuplicate2(array, mid+1, end);
	}
}

int FindLastIndexOfDuplicate(int array[], int length)
{
	return FindLastIndexOfDuplicate2(array, 0, length-1);
}
int main() {
	int n;
	cin>>n;
	int A[n];
	for(int i=0; i<n; i++)
	{
		cin>>A[i];
	}
	cout<<FindLastIndexOfDuplicate(A, n);
	return 0;
}

private static Integer getLastIndexOfLastDuplicateNumber(Integer[] arr) {
        ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(arr));

        for (int index = 0; index < numbers.size(); index++) {
            int lastDuplicateElementIndex = numbers.lastIndexOf(numbers.get(index));
            if (lastDuplicateElementIndex > -1 && lastDuplicateElementIndex != index)
                return lastDuplicateElementIndex;
        }
        return -1;
    }

We can achieve this with Time Complexity O(n) and Auxiliary Space O(1)

def findLastIndex(arr: [int]) -> int:
	last_index = -1
	for i in range(len(arr)-1):
		 if arr[i] == arr[i + 1]:
			last_index = arr[i + 1]
	return last_index

If the input is not sorted, we can still achieve this with Time Complexity O(n) and Auxiliary Space O(n).

def findLastNotOrdered(arr: [int]) -> int:
	elem_map = {}
	max_index = -1
	for i in range(len(arr)):
		if arr[i] in elem_map:
			elem_map[arr[i]].append(i)
			if len(elem_map[arr[i]]) > 1:
				max_index = i
		else:
			elem_map[arr[i]] = [i]
	return max_index

Loop through array, XOR neighbors, whenever the result is 0, store the number in that index as the last duplicate number.

Space - O(n) + O(1)
Time - O(n)

public static int findLastIndexOfDuplicateNumber(int[] arr) {
int len = arr.length - 1;
for (int i = len; i >= 0; i--) {
int j = i - 1;
if (j >= 0 && arr[i] == arr[j]) {
return i;
} else {
continue;
}

}
return -1;

}

public static int findLastIndexOfDuplicateNumber(int[] arr) {
int len = arr.length - 1;
for (int i = len; i >= 0; i--) {
int j = i - 1;
if (j >= 0 && arr[i] == arr[j]) {
return i;
} else {
continue;
}

}
return -1;

}

public static int findLastIndexOfDuplicateNumber(int[] arr) {
		int len = arr.length - 1;
		for (int i = len; i >= 0; i--) {
			int j = i - 1;
			if (j >= 0 && arr[i] == arr[j]) {
				return i;
			} else {
				continue;
			}

		}
		return -1;

	}

Anyone can right O(n), its not O(n) question and


use Binary Search on it for O(log n )