Last Coin in a Game of Alternates

Time: O(n)

Space: O(1)

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?