Triangle Area Solution

Topics Involved-: 

• Coordinate Geometry

• Basic Math

Overview

1. We are given three points that form a triangle where at least one side is strictly parallel to either the x-axis or the y-axis.
2. By identifying which two points share the same x-coordinate or y-coordinate, we can instantly determine the length of the base.
3. The height is then simply the perpendicular distance from the third point to that base, allowing us to calculate the final area.

Approach

1. Finding the Base and Height

We can check pairs of coordinates to see if they align horizontally or vertically. If two points have the same x-coordinate, the distance between their y-coordinates is the base. The height is then the horizontal distance from the remaining point to that x-axis line. We apply the same logic if two points share a y-coordinate.

2. Calculating the Area

Once we have the base and the height, we just use the standard triangle area formula:(base*height)/2 Since the problem guarantees the result will be a whole number, we can safely use integer division.

Code Implementation (Pseudocode)

function getTriangleArea(x, y):
    base = 0
    height = 0
    
    // Check for vertical alignment (parallel to y-axis)
    if x[0] == x[1]:
        base = abs(y[0] - y[1])
        height = abs(x[2] - x[0])
    else if x[1] == x[2]:
        base = abs(y[1] - y[2])
        height = abs(x[0] - x[1])
    else if x[0] == x[2]:
        base = abs(y[0] - y[2])
        height = abs(x[1] - x[0])
        
    // Check for horizontal alignment (parallel to x-axis)
    else if y[0] == y[1]:
        base = abs(x[0] - x[1])
        height = abs(y[2] - y[0])
    else if y[1] == y[2]:
        base = abs(x[1] - x[2])
        height = abs(y[0] - y[1])
    else if y[0] == y[2]:
        base = abs(y[0] - y[2])
        height = abs(y[1] - y[0])
        
    return (base * height) / 2

Time Complexity

• Time: O(1) - We only check a maximum of three pairs of coordinates, so it runs in constant time.

• Space: O(1) - Only a few variables are needed to store the base and height.

Problem-2 Email Campaign Tracker Solution

Topics Involved / Prerequisites

• SQL GROUP BY

• Aggregate Functions (SUM)

Overview

1. We need to aggregate email statistics for various marketing campaigns into a single comprehensive report.
2. This requires summing up the total emails sent and opened, grouping the results by the campaign name.
3. Finally, we calculate the unopened emails by subtracting the opened count from the sent count and sort the results alphabetically.

Approach

1. Grouping and Aggregating Assuming the data is in a table named campaign_data, we use the GROUP BY campaign_name clause to condense multiple rows into a single row per campaign. We then use the SUM() function to add up all the sent and opened emails for each group.

2. Deriving the Unopened Count SQL allows us to perform mathematical operations directly in the SELECT statement. We can find the total_emails_not_opened by simply doing SUM(emails_sent) - SUM(emails_opened) and using the AS keyword to alias our columns to the requested names. We finish with an ORDER BY clause.

SQL Query

SELECT 
    campaign_name, 
    SUM(emails_sent) AS total_emails_sent, 
    SUM(emails_opened) AS total_emails_opened, 
    (SUM(emails_sent) - SUM(emails_opened)) AS total_emails_not_opened
FROM 
    campaign_data
GROUP BY 
    campaign_name
ORDER BY 
    campaign_name ASC;

Hackerland Road Repair Solution

Topics Involved / Prerequisites

• Binary Search on Answer

• Graph Theory (Breadth-First Search)

Overview

1. We want to find the minimum cost threshold X that allows us to reach the destination within k steps.
2. Since higher budgets unlock more roads, we can binary search the answer between the minimum and maximum road repair costs.
3. For each guessed budget, we use a shortest-path algorithm like BFS to check if a valid path exists within the step limit.

Approach

1. Binary Search the Budget

Instead of trying every possible combination of roads, we guess a budget X. If X allows us to reach the destination in <=k steps, we record it as a potential answer and try a lower budget. If X fails, we know we need a higher budget.

2. BFS for Step Validation

To check if a budget X is valid, we run a Breadth-First Search (BFS) from city 1. We only traverse roads that have a repair cost <=X. We keep track of the minimum steps taken to reach each city. If we reach g_nodes in k steps or less, the budget is valid!

Code Implementatin

function canReach(n, graph, maxCost, k):
    create a queue q
    create array minSteps initialized to infinity
    
    q.push( (city: 1, steps: 0) )
    minSteps[1] = 0
    
    while q is NOT empty:
        curr = q.front()
        q.pop()
        
        if curr.city == n: return true
        if curr.steps == k: continue
        
        for each neighbor in graph[curr.city]:
            if neighbor.weight <= maxCost:
                if curr.steps + 1 < minSteps[neighbor.city]:
                    minSteps[neighbor.city] = curr.steps + 1
                    q.push( (city: neighbor.city, steps: curr.steps + 1) )
                    
    return false

function getMinCost(g_nodes, g_from, g_to, g_weight, k):
    build adjacency list 'graph' from given edges
    
    low = 0
    high = maximum value in g_weight
    ans = -1
    
    while low <= high:
        mid = low + (high - low) / 2
        
        if canReach(g_nodes, graph, mid, k):
            ans = mid
            high = mid - 1 // try to find a cheaper budget
        else:
            low = mid + 1  // need more money
            
    return ans

Time Complexity

• Time: O((V + E) log W) Where V is nodes, E is edges, and W is the maximum weight.

• Space: O(V + E) - To store the graph in an adjacency list and for the BFS queue.