Day 15 – Unique Paths, Reverse Pairs, Longest Substring Without Repeating Characters, and Starting Linked Lists

Leetcode 62 – Unique Paths

Problem: From top-left of an m x n grid, reach the bottom-right using only right/down moves.

---

1. Brute Force (Recursion)

Intuition: Try all paths recursively.

int count(int i, int j, int m, int n) {
    if (i >= m || j >= n) return 0;
    if (i == m - 1 && j == n - 1) return 1;
    return count(i + 1, j, m, n) + count(i, j + 1, m, n);
}
int uniquePaths(int m, int n) {
    return count(0, 0, m, n);
}
// TC: O(2^(m+n))
// SC: O(m + n)

---

2. DP (Memoization)

Intuition: Store results of subproblems to avoid recomputation.

int dp[101][101];
int count(int i, int j, int m, int n) {
    if (i >= m || j >= n) return 0;
    if (i == m - 1 && j == n - 1) return 1;
    if (dp[i][j] != -1) return dp[i][j];
    return dp[i][j] = count(i + 1, j, m, n) + count(i, j + 1, m, n);
}
int uniquePaths(int m, int n) {
    memset(dp, -1, sizeof(dp));
    return count(0, 0, m, n);
}
// TC: O(m*n)
// SC: O(m*n) + stack space

---

3. Optimal – Combinatorics

Intuition: The total moves = (m-1 + n-1), choose (m-1) downs out of total.

int uniquePaths(int m, int n) {
    int N = m + n - 2, r = m - 1;
    double res = 1;
    for (int i = 1; i <= r; i++) {
        res = res * (N - r + i) / i;
    }
    return (int)res;
}
// TC: O(min(m, n))
// SC: O(1)

---

Leetcode 493 – Reverse Pairs

Problem: Count pairs i < j such that nums[i] > 2 * nums[j]

---

1. Brute Force

int reversePairs(vector<int>& nums) {
    int count = 0;
    for (int i = 0; i < nums.size(); i++)
        for (int j = i + 1; j < nums.size(); j++)
            if ((long long)nums[i] > 2LL * nums[j]) count++;
    return count;
}
// TC: O(n²)
// SC: O(1)

---

2. Optimal – Modified Merge Sort

Intuition: Same as counting inversions. Count while merging.

int merge(vector<int>& nums, int low, int mid, int high) {
    int cnt = 0, j = mid + 1;
    for (int i = low; i <= mid; i++) {
        while (j <= high && (long long)nums[i] > 2LL * nums[j]) j++;
        cnt += (j - (mid + 1));
    }

    vector<int> temp;
    int left = low, right = mid + 1;
    while (left <= mid && right <= high) {
        if (nums[left] <= nums[right]) temp.push_back(nums[left++]);
        else temp.push_back(nums[right++]);
    }
    while (left <= mid) temp.push_back(nums[left++]);
    while (right <= high) temp.push_back(nums[right++]);
    for (int i = low; i <= high; i++) nums[i] = temp[i - low];
    return cnt;
}

int mergeSort(vector<int>& nums, int low, int high) {
    if (low >= high) return 0;
    int mid = (low + high) / 2;
    int inv = mergeSort(nums, low, mid);
    inv += mergeSort(nums, mid + 1, high);
    inv += merge(nums, low, mid, high);
    return inv;
}

int reversePairs(vector<int>& nums) {
    return mergeSort(nums, 0, nums.size() - 1);
}
// TC: O(n log n)
// SC: O(n)

---

Leetcode 3 – Longest Substring Without Repeating Characters

---

1. Brute Force

Intuition: Check all substrings.

int lengthOfLongestSubstring(string s) {
    int maxLen = 0;
    for (int i = 0; i < s.size(); i++) {
        set<char> st;
        for (int j = i; j < s.size(); j++) {
            if (st.count(s[j])) break;
            st.insert(s[j]);
            maxLen = max(maxLen, j - i + 1);
        }
    }
    return maxLen;
}
// TC: O(n²)
// SC: O(n)

---

2. Optimal – Sliding Window with Map

Intuition: Use map to track last seen indices.

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> mp;
    int l = 0, r = 0, maxLen = 0;
    while (r < s.size()) {
        if (mp.count(s[r])) l = max(mp[s[r]] + 1, l);
        mp[s[r]] = r;
        maxLen = max(maxLen, r - l + 1);
        r++;
    }
    return maxLen;
}
// TC: O(n)
// SC: O(n)

---

Linked List Basics

---

➤ Definition using Struct

struct Node {
    int data;
    Node* next;
    Node(int val) {
        data = val;
        next = NULL;
    }
};

➤ Using Class

class Node {
public:
    int data;
    Node* next;
    Node(int val) {
        data = val;
        next = NULL;
    }
};

---

Convert Array to Linked List

Node* convert(vector<int>& arr) {
    Node* head = new Node(arr[0]);
    Node* temp = head;
    for (int i = 1; i < arr.size(); i++) {
        temp->next = new Node(arr[i]);
        temp = temp->next;
    }
    return head;
}

---

Linked List Operations

---

➤ Traversal and Count

int countNodes(Node* head) {
    int cnt = 0;
    while (head != NULL) {
        cnt++;
        head = head->next;
    }
    return cnt;
}

---

➤ Search

bool search(Node* head, int val) {
    while (head != NULL) {
        if (head->data == val) return true;
        head = head->next;
    }
    return false;
}

---

➤ Delete Head

Node* deleteHead(Node* head) {
    if (head == NULL) return NULL;
    Node* temp = head;
    head = head->next;
    delete temp;
    return head;
}

---

➤ Delete Tail

Node* deleteTail(Node* head) {
    if (head == NULL || head->next == NULL) return NULL;
    Node* temp = head;
    while (temp->next->next != NULL) temp = temp->next;
    delete temp->next;
    temp->next = NULL;
    return head;
}

---

➤ Delete kth Node (1-based index)

Node* deleteK(Node* head, int k) {
    if (k == 1) return deleteHead(head);
    Node* temp = head;
    for (int i = 1; i < k - 1; i++) {
        if (temp == NULL) return head;
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL) return head;
    Node* del = temp->next;
    temp->next = temp->next->next;
    delete del;
    return head;
}

---

➤ Delete Node by Value

Node* deleteVal(Node* head, int val) {
    if (head == NULL) return NULL;
    if (head->data == val) return deleteHead(head);
    Node* temp = head;
    while (temp->next != NULL && temp->next->data != val) {
        temp = temp->next;
    }
    if (temp->next != NULL) {
        Node* del = temp->next;
        temp->next = temp->next->next;
        delete del;
    }
    return head;
}

---

Important Note

Always check edge cases in Linked Lists:

• Deleting head/tail of single-element list

• NULL pointer accesses

• kth node exceeding length

• Empty list checks