Module 3: UPER

U - Understand

In this first phase, your goal is to thoroughly understand the problem before attempting to solve it.

• Read the problem statement multiple times
• Identify the inputs and expected outputs
• List all constraints and edge cases
• Clarify any ambiguous aspects of the problem
• Create simple examples to confirm your understanding

Example questions to ask during this phase:

• What exactly am I being asked to do?
• What are the inputs to this problem?
• What output is expected?
• Are there any constraints I need to be aware of?
• What are the edge cases I need to handle?

P - Plan

Once you understand the problem, develop a clear strategy for how to solve it before writing any code.

• Break the problem down into smaller sub-problems
• Consider multiple approaches and algorithms
• Evaluate the time and space complexity of each approach
• Choose the most appropriate data structures
• Sketch the solution using pseudocode or flowcharts

Example planning activities:

• Write high-level pseudocode outlining the steps
• Draw a flowchart of the algorithm
• List the data structures you'll need
• Determine any helper functions that might be useful
• Estimate the computational complexity of your approach

E - Execute

With a plan in place, now implement your solution by writing clean, organized code.

• Translate your plan into actual code
• Follow your programming language's best practices
• Write code in small, testable increments
• Test each component as you build it
• Look for opportunities to refactor and improve

Execution tips:

• Focus on one sub-problem at a time
• Use meaningful variable and function names
• Include appropriate comments to explain your logic
• Test with the examples you created during the Understanding phase
• Track your progress against your plan

R - Reflect

After implementing your solution, evaluate its effectiveness and look for ways to improve it.

• Test your solution with various inputs including edge cases
• Analyze the time and space complexity
• Identify any inefficiencies or bugs
• Consider alternative implementations
• Document what you learned for future reference

Reflection questions:

• Does my solution correctly handle all inputs and edge cases?
• Is this the most efficient solution possible?
• Can I optimize for better time or space complexity?
• Is my code clean, well-structured, and maintainable?
• What did I learn that I can apply to future problems?

Understand

• Input: An array of integers and a target sum
• Output: Indices of the two numbers that add up to the target
• Constraints: Each input has exactly one solution, can't use same element twice
• Example: Input: [2, 7, 11, 15], target = 9; Output: [0, 1] (2 + 7 = 9)

Plan

Two main approaches:

1. Brute Force: Check every pair of numbers (O(n²) time)
2. Hash Map Approach: Store elements in a hash map and check for complements (O(n) time)

I'll use the Hash Map approach for better efficiency:

1. Create a hash map to store value-index pairs
2. Iterate through the array
3. For each element, calculate its complement (target - current)
4. Check if the complement exists in the hash map
5. If found, return the indices; if not, add current element to the map

Execute

public int[] twoSum(int[] nums, int target) {
    // Create hash map to store value-index pairs
    HashMap<Integer, Integer> map = new HashMap<>();
    
    // Iterate through the array
    for (int i = 0; i < nums.length; i++) {
        // Calculate the complement
        int complement = target - nums[i];
        
        // Check if complement exists in map
        if (map.containsKey(complement)) {
            // Return indices of the two numbers
            return new int[] { map.get(complement), i };
        }
        
        // Add current element to map
        map.put(nums[i], i);
    }
    
    // No solution found (per problem constraints, shouldn't happen)
    throw new IllegalArgumentException("No two sum solution");
}
                    

Reflect

• Correctness: The solution correctly finds pairs that sum to the target
• Time Complexity: O(n) - we only need to traverse the array once
• Space Complexity: O(n) - the hash map could potentially store all elements
• Alternative Approach: Could sort the array and use two pointers, but that would be O(n log n)
• Learning: This demonstrates how using appropriate data structures (hash map) can dramatically improve efficiency