Pattern 20: Prefix Sum

Arpit Rathore — Fri, 03 Jan 2025 03:21:45 +0000

List of problems I have solved so far
- Easy
- Medium
- Hard

List of problems I have solved so far

Easy

Question	Solution	Date	Comment
	Solution
	Solution
	Solution

Medium

Question	Solution	Date	Comment
	Solution
	Solution
	Solution
	Solution

Hard

Question	Solution	Date	Comment
	Solution
	Solution
	Solution
	Solution

Tips and tricks

Arpit Rathore — Mon, 23 Dec 2024 04:51:20 +0000

Visualization helpers

Arpit Rathore — Mon, 23 Dec 2024 04:50:05 +0000

Visualization helper methods
- 1. Two pointers
- 2. Sliding Window
- 3. Binary Search
- 4. Two dimension Array
- 5. Print Linked list
- 6. Print Binary Tree

Visualization helper methods

I have created few helper methods to visualize a data structure during an algorithm.

1. Two pointers

int[] : Integer Array

// Helper method to visualize two pointers for int[]
private void tpi(int[] s, int l, int r, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);
    for (int i = 0; i < s.length; i++) {
        if (i == l && i == r) {
            System.out.printf("[(%s)]", s[i]);
        } else if (i == l) {
            System.out.printf("(%s)", s[i]);
        } else if (i == r) {
            System.out.printf("[%s]", s[i]);
        } else {
            System.out.print(s[i]);
        }
        System.out.print(" ");
    }
    System.out.printf("| l=%s, r=%s %n", l, r);
}

char[] : Character Array

// Helper method to visualize two pointers for char[]
private void tpc(char[] s, int l, int r, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);
    for (int i = 0; i < s.length; i++) {
        if (i == l && i == r) {
            System.out.printf("[(%s)]", s[i]);
        } else if (i == l) {
            System.out.printf("(%s)", s[i]);
        } else if (i == r) {
            System.out.printf("[%s]", s[i]);
        } else {
            System.out.print(s[i]);
        }
        System.out.print(" ");
    }
    System.out.printf("| l=%s, r=%s %n", l, r);
}

String : String

// Helper method to visualize two pointers for String
private void tps(String s, int l, int r, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);
    for (int i = 0; i < s.length(); i++) {
        if (i == l && i == r) {
            System.out.printf("[(%s)]", s.charAt(i));
        } else if (i == l) {
            System.out.printf("(%s)", s.charAt(i));
        } else if (i == r) {
            System.out.printf("[%s]", s.charAt(i));
        } else {
            System.out.print(s.charAt(i));
        }
        System.out.print(" ");
    }
    System.out.printf("| l=%s, r=%s %n", l, r);
}

2. Sliding Window

int[] : Integer Array

// Helper method to visualize sliding window for int[]
private void swi(int[] nums, int l, int r, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);
    for (int i = 0; i < nums.length; i++) {
        if (i == l) {
            System.out.print("[");
        }
        System.out.print(nums[i]);
        if (i == r) {
            System.out.print("]");
        }
        System.out.print(" ");
    }
    System.out.printf("| l=%s, r=%s %n", l, r);
}

char[] : Character Array

// Helper method to visualize sliding window for char[]
private void swi(char[] chars, int l, int r, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);
    for (int i = 0; i < chars.length; i++) {
        if (i == l) {
            System.out.print("[");
        }
        System.out.print(chars[i]);
        if (i == r) {
            System.out.print("]");
        }
        System.out.print(" ");
    }
    System.out.printf("| l=%s, r=%s %n", l, r);
}

String : String

// Helper method to visualize sliding window for String
private void sws(String s, int l, int r, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);
    for (int i = 0; i < s.length(); i++) {
        if (i == l) {
            System.out.print("[");
        }
        System.out.print(s.charAt(i));
        if (i == r) {
            System.out.print("]");
        }
        System.out.print(" ");
    }
    System.out.printf("| l=%s, r=%s %n", l, r);
}

3. Binary Search

// Helper method to visualize binary search (how pointers are moving)
private void pbs(int[] a, int m, int l, int r, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);
    System.out.printf("L: %s, M: %s, R: %s | ", l, m, r);
    for (int i = 0; i < a.length; i++) {
        if (i == m) {
            if (m == l && m == r) {
                System.out.printf("[({%s})]", a[i]);
            } else if (m == l) {
                System.out.printf("({%s})", a[i]);
            } else if (m == r) {
                System.out.printf("[{%s}]", a[i]);
            } else {
                System.out.printf("{%s}", a[i]);
            }
        } else if (i == l && i == r) {
            System.out.printf("[(%s)]", a[i]);
        } else if (i == l) {
            System.out.printf("(%s)", a[i]);
        } else if (i == r) {
            System.out.printf("[%s]", a[i]);
        } else {
            System.out.print(a[i]);
        }
        System.out.print(" ");
    }
    System.out.println();
}

4. Two dimension Array

int[][] : Integer Array

// Helper method to visualize two dimesional int array int[][]
private void tdi(int[][] a) {
    for (int[] row : a) {
        System.out.println(Arrays.toString(row));
    }
    System.out.println("---");
}

char[][] : Character Array

// Helper method to visualize two dimesional char array char[][]
private void tdc(char[][] a) {
    for (char[] row : a) {
        System.out.println(Arrays.toString(row));
    }
    System.out.println("---");
}

String[][] : String

// Helper method to visualize two dimesional String array String[][]
private void tds(String[][] a) {
    for (String[] row : a) {
        System.out.println(Arrays.toString(row));
    }
    System.out.println("---");
}

5. Print Linked list

// Helper method to visualize LinkedList
private void pll(ListNode head, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);

    int size = 0;
    ListNode curr = head;
    while (curr != null) {
        size++;
        curr = curr.next;
    }

    curr = head;
    int i = 0;
    while (curr != null) {
        if (i == size / 2) {
            System.out.printf("[%s] -> ", curr.val);
        } else {
            System.out.printf("%s -> ", curr.val);
        }
        curr = curr.next;
        i++;
    }
    System.out.print("null\n");
}

6. Print Binary Tree

// Helper method to visualize bianry tree
private void pbt(final TreeNode node) {
    String result = ppt(node, new StringBuilder(), true, new StringBuilder());
    System.out.println(result);
}

private String pbtUtil(TreeNode node, StringBuilder prefix, boolean isTail, StringBuilder sb) {
    if (node.right != null) {
      pbtUtil(node.right, new StringBuilder().append(prefix).append(isTail ? "│   " : "    "), false,
          sb);
    }
    sb.append(prefix).append(isTail ? "└── " : "┌── ").append(node.val).append("\n");
    if (node.left != null) {
      pbtUtil(node.left, new StringBuilder().append(prefix).append(isTail ? "    " : "│   "), true, sb);
    }
    return sb.toString();
}

239. Sliding Window Maximum - Monotonic stack

Arpit Rathore — Thu, 19 Dec 2024 10:56:21 +0000

85. Maximal Rectangle

Arpit Rathore — Thu, 19 Dec 2024 10:55:42 +0000

84. Largest Rectangle in Histogram

Arpit Rathore — Thu, 19 Dec 2024 10:55:23 +0000

901. Online Stock Span

Arpit Rathore — Thu, 19 Dec 2024 10:55:04 +0000

739. Daily Temperatures

Arpit Rathore — Thu, 19 Dec 2024 10:54:46 +0000

503. Next Greater Element II

Arpit Rathore — Thu, 19 Dec 2024 10:54:32 +0000

496. Next Greater Element I

Arpit Rathore — Thu, 19 Dec 2024 10:51:48 +0000

402. Remove K Digits

Arpit Rathore — Thu, 19 Dec 2024 10:51:32 +0000

316. Remove Duplicate Letters

Arpit Rathore — Thu, 19 Dec 2024 10:51:10 +0000

DEV Community: Arpit Rathore