Weekly Coding Challenge #3: Contains Duplicate (+ Challenge #2 Solution)

This Week. Contains Duplicate

Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.

Constraints: 1 <= nums.length <= 10^5, -10^9 <= nums[i] <= 10^9

Example 1: nums = [1,2,3,1] → true 

Example 2: nums = [1,2,3,4] → false

Can you beat O(n²)?

Practical applications

 "Have I seen this before?" is everywhere: de-duplicating records in a data pipeline, spotting repeated transaction IDs in fraud checks, and idempotency keys in APIs.

The solution and Challenge #4 drop next Sunday.

Solution to Challenge #2: Best Time to Buy and Sell Stock

Given prices[i], the price on day i, pick one day to buy and a later day to sell for maximum profit (return 0 if none). Instead of checking every pair (O(n²)), scan once while tracking the lowest price seen so far; at each day, the best profit is price - minSoFar.

java

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE; // cheapest buy price so far
        int maxProfit = 0;                // best profit so far

        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;  // better day to buy
            } else
                // sell today?
                maxProfit = Math.max(maxProfit, price - minPrice); 
        }
        return maxProfit;
    }
}

Complexity: O(n) time, O(1) space.

References

LeetCode. (n.d.). 121. Best Time to Buy and Sell Stock. LeetCode. https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

LeetCode. (n.d.). 217. Contains Duplicate. LeetCode. https://leetcode.com/problems/contains-duplicate/