Last Coin in a Game of Alternates

Time: O(n)

Space: O(1)

Problem Overview

The implementation repeatedly compares the two ends and discards one side each step.

Intuition

The implementation repeatedly compares the two ends and discards one side each step. If left value is greater than or equal to right, it advances left; otherwise it decreases right. This elimination continues until only one index remains, which is returned as the last coin value.

Algorithm

1Initialise two pointers i = 0 and j = n - 1.
2While i < j:
3 If arr[i] >= arr[j], increment i.
4 Else decrement j.
5When pointers meet, return arr[i] (or arr[j], same index).

Example Walkthrough

Input: arr = [5, 2, 9, 1, 7]

1. i=0 (5), j=4 (7): 5<7 so j-- -> 3.
2. i=0 (5), j=3 (1): 5>=1 so i++ -> 1.
3. i=1 (2), j=3 (1): 2>=1 so i++ -> 2.
4. i=2 (9), j=3 (1): 9>=1 so i++ -> 3. Pointers meet at index 3.

Output: 1

Common Pitfalls

• This explanation follows the current elimination logic exactly; if game rules differ, update logic and explanation together.
• Use while(i < j); using <= can move pointers past each other and break return index.
• Requires non-empty input array; otherwise pointer initialization is invalid.

Last Coin in a Game of Alternates.java

Java


// Approach: Two pointers from both ends. Compare arr[i] and arr[j], then discard one end each turn.
// Continue until pointers meet; the remaining position is the last coin according to this elimination rule.
// Time: O(n) Space: O(1)

class Solution {

    public int coin(int[] arr) {
        int n = arr.length;
        int i = 0, j = n - 1;

        while (i < j) {
            if (arr[i] >= arr[j]) {
                i++; 
            }else {
                j--;
            }
        }
        return arr[i];
    }
}

Was this solution helpful?