Oct 5, 2022 · Oct 5, 2022 · Oct 5, 2022 · Oct 5, 2022 · Oct 5, 2022 · Oct 5, 2022
diff --git a/.github/workflows/contributors.yml b/.github/workflows/contributors.yml
 name: Add contributors
 on:
  schedule:
    - cron:  '20 20 * * *'
  push:
    branches:
      - main

 jobs:
  add-contributors:
    runs-on: ubuntu-latest
    steps:
    - uses: actions/checkout@v2
    - uses: BobAnkh/add-contributors@master
      with:
        CONTRIBUTOR: '### Contributors'
        COLUMN_PER_ROW: '6'
        ACCESS_TOKEN: ${{secrets.GITHUB_TOKEN}}
        IMG_WIDTH: '100'
        FONT_SIZE: '14'
        PATH: '/README.md'
        COMMIT_MESSAGE: 'docs(README): update contributors'
        AVATAR_SHAPE: 'round'
diff --git a/1048-longest-string-chain/1048-longest-string-chain.java b/1048-longest-string-chain/1048-longest-string-chain.java
 class Solution {
    public int longestStrChain(String[] words) {
        Map<String,Integer> map = new HashMap<>();
        Arrays.sort(words, (a,b)->a.length() - b.length());
        int res = 0;
        for(String word : words)
        {
            int best = 0;
            for(int i=0;i<word.length();i++)
            {
                String prev = word.substring(0,i) + word.substring(i+1);
                best = Math.max(best,map.getOrDefault(prev,0)+1);
            }
            map.put(word,best);
            res = Math.max(res,best);
        }
        return res;
    }
 }
diff --git a/1048-longest-string-chain/README.md b/1048-longest-string-chain/README.md
 <h2><a href="https://leetcode.com/problems/longest-string-chain/">1048. Longest String Chain</a></h2><h3>Medium</h3><hr><div><p>You are given an array of <code>words</code> where each word consists of lowercase English letters.</p>

 <p><code>word<sub>A</sub></code> is a <strong>predecessor</strong> of <code>word<sub>B</sub></code> if and only if we can insert <strong>exactly one</strong> letter anywhere in <code>word<sub>A</sub></code> <strong>without changing the order of the other characters</strong> to make it equal to <code>word<sub>B</sub></code>.</p>

 <ul>
 <li>For example, <code>"abc"</code> is a <strong>predecessor</strong> of <code>"ab<u>a</u>c"</code>, while <code>"cba"</code> is not a <strong>predecessor</strong> of <code>"bcad"</code>.</li>
 </ul>

 <p>A <strong>word chain</strong><em> </em>is a sequence of words <code>[word<sub>1</sub>, word<sub>2</sub>, ..., word<sub>k</sub>]</code> with <code>k &gt;= 1</code>, where <code>word<sub>1</sub></code> is a <strong>predecessor</strong> of <code>word<sub>2</sub></code>, <code>word<sub>2</sub></code> is a <strong>predecessor</strong> of <code>word<sub>3</sub></code>, and so on. A single word is trivially a <strong>word chain</strong> with <code>k == 1</code>.</p>

 <p>Return <em>the <strong>length</strong> of the <strong>longest possible word chain</strong> with words chosen from the given list of </em><code>words</code>.</p>

 <p>&nbsp;</p>
 <p><strong>Example 1:</strong></p>

 <pre><strong>Input:</strong> words = ["a","b","ba","bca","bda","bdca"]
 <strong>Output:</strong> 4
 <strong>Explanation</strong>: One of the longest word chains is ["a","<u>b</u>a","b<u>d</u>a","bd<u>c</u>a"].
 </pre>

 <p><strong>Example 2:</strong></p>

 <pre><strong>Input:</strong> words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
 <strong>Output:</strong> 5
 <strong>Explanation:</strong> All the words can be put in a word chain ["xb", "xb<u>c</u>", "<u>c</u>xbc", "<u>p</u>cxbc", "pcxbc<u>f</u>"].
 </pre>

 <p><strong>Example 3:</strong></p>

 <pre><strong>Input:</strong> words = ["abcd","dbqca"]
 <strong>Output:</strong> 1
 <strong>Explanation:</strong> The trivial word chain ["abcd"] is one of the longest word chains.
 ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.
 </pre>

 <p>&nbsp;</p>
 <p><strong>Constraints:</strong></p>

 <ul>
 <li><code>1 &lt;= words.length &lt;= 1000</code></li>
 <li><code>1 &lt;= words[i].length &lt;= 16</code></li>
 <li><code>words[i]</code> only consists of lowercase English letters.</li>
 </ul>
 </div>
diff --git a/121 Leetcode/114-flatten-binary-tree-to-linked-list.cpp b/121 Leetcode/114-flatten-binary-tree-to-linked-list.cpp
 class Solution {
 public:
    void flatten(TreeNode* root) {
        if(!root) return;
        while(root)
        {
            TreeNode* temp = root->right;
            root->right = root->left;
            root->left = NULL;
           TreeNode* node = root;
            while(node->right)
            {
                node = node->right;
            }
            node->right = temp;
            root = root->right;
        }
    }
 };
diff --git a/121 Leetcode/121 leetcode.py b/121 Leetcode/121 leetcode.py
 class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxProfit = 0
        currentMax = 0

        for i in reversed(prices):
            currentMax = max(currentMax, i)
            profit = currentMax - i
            maxProfit = max(profit, maxProfit)
        return maxProfit
diff --git a/121 Leetcode/word-ladder-ii.cpp b/121 Leetcode/word-ladder-ii.cpp
 // BFS gives TLE if we store path while traversing because whenever we find a better visit time for a word, we have to clear/make a new path vector everytime.
 // The idea is to first use BFS to search from beginWord to endWord and generate the word-to-children mapping at the same time.
 // Then, use DFS (backtracking) to generate the transformation sequences according to the mapping.
 // The reverse DFS allows us to only make the shortest paths, never having to clear a whole sequence when we encounter better result in BFS
 // No string operations are done, by dealing with indices instead.



 class Solution {
 public:
 bool able(string s,string t){
    int c=0;
    for(int i=0;i<s.length();i++)
        c+=(s[i]!=t[i]);
    return c==1;
 }
 void bfs(vector<vector<int>> &g,vector<int> parent[],int n,int start,int end){
    vector <int> dist(n,1005);
    queue <int> q;
    q.push(start);
    parent[start]={-1};
    dist[start]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int u:g[x]){
            if(dist[u]>dist[x]+1){
                dist[u]=dist[x]+1;
                q.push(u);
                parent[u].clear();
                parent[u].push_back(x);
            }
            else if(dist[u]==dist[x]+1)
                parent[u].push_back(x);
        }
    }
 }
 void shortestPaths(vector<vector<int>> &Paths, vector<int> &path, vector<int> parent[],int node){
    if(node==-1){
        // as parent of start was -1, we've completed the backtrack
        Paths.push_back(path);
        return ;
    }
    for(auto u:parent[node]){
        path.push_back(u);
        shortestPaths(Paths,path,parent,u);
        path.pop_back();
    }
 }
 vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
    // start and end are indices of beginWord and endWord
    int n=wordList.size(),start=-1,end=-1;
    vector<vector<string>> ANS;
    for(int i=0;i<n;i++){
        if(wordList[i]==beginWord)
            start=i;
        if(wordList[i]==endWord)
            end=i;
    }

    // if endWord doesn't exist, return empty list
    if(end==-1)
        return ANS;

    // if beginWord doesn't exist, add it in start of WordList
    if(start==-1){
        wordList.emplace(wordList.begin(),beginWord);
        start=0;
        end++;
        n++;
    }
    // for each word, we're making adjency list of neighbour words (words that can be made with one letter change)
    // Paths will store all the shortest paths (formed later by backtracking)
    vector<vector<int>> g(n,vector<int>()),Paths;

    // storing possible parents for each word (to backtrack later), path is the current sequence (while backtracking)
    vector<int> parent[n],path;

    // creating adjency list for each pair of words in the wordList (including beginword)
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)
            if(able(wordList[i],wordList[j])){
                g[i].push_back(j);
                g[j].push_back(i);
            }

    bfs(g,parent,n,start,end);

    // backtracking to make shortestpaths
    shortestPaths(Paths,path,parent,end);
    for(auto u:Paths){
        vector <string> now;
        for(int i=0;i<u.size()-1;i++)
            now.push_back(wordList[u[i]]);
        reverse(now.begin(),now.end());
        now.push_back(wordList[end]);
        ANS.push_back(now);
    }
    return ANS;
 }
 };
diff --git a/1480-running-sum-of-1d-array/1480-running-sum-of-1d-array.cpp b/1480-running-sum-of-1d-array/1480-running-sum-of-1d-array.cpp
 class Solution {
 public:
    vector<int> runningSum(vector<int>& nums) {
        for(int i=1;i<nums.size();i++)
            nums[i]+= nums[i-1];
        return nums;
    }
 };
diff --git a/1480-running-sum-of-1d-array/1480-running-sum-of-1d-array.java b/1480-running-sum-of-1d-array/1480-running-sum-of-1d-array.java
 class Solution {
    public int[] runningSum(int[] nums) {
        for(int i=1;i<nums.length;i++)
           nums[i]+=nums[i-1];
        return nums;
    }
 }
diff --git a/1480-running-sum-of-1d-array/NOTES.md b/1480-running-sum-of-1d-array/NOTES.md

diff --git a/1480-running-sum-of-1d-array/README.md b/1480-running-sum-of-1d-array/README.md
 <h2><a href="https://leetcode.com/problems/running-sum-of-1d-array/">1480. Running Sum of 1d Array</a></h2><h3>Easy</h3><hr><div><p>Given an array <code>nums</code>. We define a running sum of an array as&nbsp;<code>runningSum[i] = sum(nums[0]…nums[i])</code>.</p>

 <p>Return the running sum of <code>nums</code>.</p>

 <p>&nbsp;</p>
 <p><strong>Example 1:</strong></p>

 <pre><strong>Input:</strong> nums = [1,2,3,4]
 <strong>Output:</strong> [1,3,6,10]
 <strong>Explanation:</strong> Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].</pre>

 <p><strong>Example 2:</strong></p>

 <pre><strong>Input:</strong> nums = [1,1,1,1,1]
 <strong>Output:</strong> [1,2,3,4,5]
 <strong>Explanation:</strong> Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].</pre>

 <p><strong>Example 3:</strong></p>

 <pre><strong>Input:</strong> nums = [3,1,2,10,1]
 <strong>Output:</strong> [3,4,6,16,17]
 </pre>

 <p>&nbsp;</p>
 <p><strong>Constraints:</strong></p>

 <ul>
 <li><code>1 &lt;= nums.length &lt;= 1000</code></li>
 <li><code>-10^6&nbsp;&lt;= nums[i] &lt;=&nbsp;10^6</code></li>
 </ul></div>
diff --git a/1642-furthest-building-you-can-reach/1642-furthest-building-you-can-reach.java b/1642-furthest-building-you-can-reach/1642-furthest-building-you-can-reach.java
 class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0;i<heights.length-1;i++)
        {
            int distance = heights[i+1] - heights[i];
            if(distance>0)
                pq.add(distance);
            if(pq.size()>ladders)
                bricks -= pq.poll();
            if(bricks<0)
                return i;
        }
        return heights.length-1;
    }
 }
diff --git a/1642-furthest-building-you-can-reach/NOTES.md b/1642-furthest-building-you-can-reach/NOTES.md

diff --git a/1642-furthest-building-you-can-reach/README.md b/1642-furthest-building-you-can-reach/README.md
 <h2><a href="https://leetcode.com/problems/furthest-building-you-can-reach/">1642. Furthest Building You Can Reach</a></h2><h3>Medium</h3><hr><div><p>You are given an integer array <code>heights</code> representing the heights of buildings, some <code>bricks</code>, and some <code>ladders</code>.</p>

 <p>You start your journey from building <code>0</code> and move to the next building by possibly using bricks or ladders.</p>

 <p>While moving from building <code>i</code> to building <code>i+1</code> (<strong>0-indexed</strong>),</p>

 <ul>
 <li>If the current building's height is <strong>greater than or equal</strong> to the next building's height, you do <strong>not</strong> need a ladder or bricks.</li>
 <li>If the current building's height is <b>less than</b> the next building's height, you can either use <strong>one ladder</strong> or <code>(h[i+1] - h[i])</code> <strong>bricks</strong>.</li>
 </ul>

 <p><em>Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.</em></p>

 <p>&nbsp;</p>
 <p><strong>Example 1:</strong></p>
 <img alt="" src="https://assets.leetcode.com/uploads/2020/10/27/q4.gif" style="width: 562px; height: 561px;">
 <pre><strong>Input:</strong> heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
 <strong>Output:</strong> 4
 <strong>Explanation:</strong> Starting at building 0, you can follow these steps:
 - Go to building 1 without using ladders nor bricks since 4 &gt;= 2.
 - Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 &lt; 7.
 - Go to building 3 without using ladders nor bricks since 7 &gt;= 6.
 - Go to building 4 using your only ladder. You must use either bricks or ladders because 6 &lt; 9.
 It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
 </pre>

 <p><strong>Example 2:</strong></p>

 <pre><strong>Input:</strong> heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
 <strong>Output:</strong> 7
 </pre>

 <p><strong>Example 3:</strong></p>

 <pre><strong>Input:</strong> heights = [14,3,19,3], bricks = 17, ladders = 0
 <strong>Output:</strong> 3
 </pre>

 <p>&nbsp;</p>
 <p><strong>Constraints:</strong></p>

 <ul>
 <li><code>1 &lt;= heights.length &lt;= 10<sup>5</sup></code></li>
 <li><code>1 &lt;= heights[i] &lt;= 10<sup>6</sup></code></li>
 <li><code>0 &lt;= bricks &lt;= 10<sup>9</sup></code></li>
 <li><code>0 &lt;= ladders &lt;= heights.length</code></li>
 </ul>
 </div>
diff --git a/19-remove-nth-node-from-end-of-list.cpp/19-remove-nth-node-from-end-of-list.cpp b/19-remove-nth-node-from-end-of-list.cpp/19-remove-nth-node-from-end-of-list.cpp
 /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 class Solution {
 public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int cnt=0;
        ListNode* curr=head;
        while(curr){
            curr=curr->next;
            cnt++;
        }curr=head;
        if(n==1 && cnt==1)
            return NULL;
        if(cnt-n==0)
            return head->next;
        for(int i=1;i<cnt-n;i++){
            curr=curr->next;
        }
        if(curr->next==NULL)
            return head;
        if(curr->next->next==NULL)
            curr->next=NULL;
        else
            curr->next=curr->next->next;
        return  head;
    }
 };
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,23 @@
		name: Add contributors
		on:
		schedule:
		- cron: '20 20 * * *'
		push:
		branches:
		- main

		jobs:
		add-contributors:
		runs-on: ubuntu-latest
		steps:
		- uses: actions/checkout@v2
		- uses: BobAnkh/add-contributors@master
		with:
		CONTRIBUTOR: '### Contributors'
		COLUMN_PER_ROW: '6'
		ACCESS_TOKEN: ${{secrets.GITHUB_TOKEN}}
		IMG_WIDTH: '100'
		FONT_SIZE: '14'
		PATH: '/README.md'
		COMMIT_MESSAGE: 'docs(README): update contributors'
		AVATAR_SHAPE: 'round'
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,19 @@
		class Solution {
		public int longestStrChain(String[] words) {
		Map<String,Integer> map = new HashMap<>();
		Arrays.sort(words, (a,b)->a.length() - b.length());
		int res = 0;
		for(String word : words)
		{
		int best = 0;
		for(int i=0;i<word.length();i++)
		{
		String prev = word.substring(0,i) + word.substring(i+1);
		best = Math.max(best,map.getOrDefault(prev,0)+1);
		}
		map.put(word,best);
		res = Math.max(res,best);
		}
		return res;
		}
		}
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,44 @@
		<h2><a href="https://leetcode.com/problems/longest-string-chain/">1048. Longest String Chain</a></h2><h3>Medium</h3><hr><div><p>You are given an array of <code>words</code> where each word consists of lowercase English letters.</p>

		<p><code>word<sub>A</sub></code> is a <strong>predecessor</strong> of <code>word<sub>B</sub></code> if and only if we can insert <strong>exactly one</strong> letter anywhere in <code>word<sub>A</sub></code> <strong>without changing the order of the other characters</strong> to make it equal to <code>word<sub>B</sub></code>.</p>

		<ul>
		<li>For example, <code>"abc"</code> is a <strong>predecessor</strong> of <code>"ab<u>a</u>c"</code>, while <code>"cba"</code> is not a <strong>predecessor</strong> of <code>"bcad"</code>.</li>
		</ul>

		<p>A <strong>word chain</strong><em> </em>is a sequence of words <code>[word<sub>1</sub>, word<sub>2</sub>, ..., word<sub>k</sub>]</code> with <code>k >= 1</code>, where <code>word<sub>1</sub></code> is a <strong>predecessor</strong> of <code>word<sub>2</sub></code>, <code>word<sub>2</sub></code> is a <strong>predecessor</strong> of <code>word<sub>3</sub></code>, and so on. A single word is trivially a <strong>word chain</strong> with <code>k == 1</code>.</p>

		<p>Return <em>the <strong>length</strong> of the <strong>longest possible word chain</strong> with words chosen from the given list of </em><code>words</code>.</p>

		<p> </p>
		<p><strong>Example 1:</strong></p>

		<pre><strong>Input:</strong> words = ["a","b","ba","bca","bda","bdca"]
		<strong>Output:</strong> 4
		<strong>Explanation</strong>: One of the longest word chains is ["a","<u>b</u>a","b<u>d</u>a","bd<u>c</u>a"].
		</pre>

		<p><strong>Example 2:</strong></p>

		<pre><strong>Input:</strong> words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
		<strong>Output:</strong> 5
		<strong>Explanation:</strong> All the words can be put in a word chain ["xb", "xb<u>c</u>", "<u>c</u>xbc", "<u>p</u>cxbc", "pcxbc<u>f</u>"].
		</pre>

		<p><strong>Example 3:</strong></p>

		<pre><strong>Input:</strong> words = ["abcd","dbqca"]
		<strong>Output:</strong> 1
		<strong>Explanation:</strong> The trivial word chain ["abcd"] is one of the longest word chains.
		["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.
		</pre>

		<p> </p>
		<p><strong>Constraints:</strong></p>

		<ul>
		<li><code>1 <= words.length <= 1000</code></li>
		<li><code>1 <= words[i].length <= 16</code></li>
		<li><code>words[i]</code> only consists of lowercase English letters.</li>
		</ul>
		</div>
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,19 @@
		class Solution {
		public:
		void flatten(TreeNode* root) {
		if(!root) return;
		while(root)
		{
		TreeNode* temp = root->right;
		root->right = root->left;
		root->left = NULL;
		TreeNode* node = root;
		while(node->right)
		{
		node = node->right;
		}
		node->right = temp;
		root = root->right;
		}
		}
		};
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,10 @@
		class Solution:
		def maxProfit(self, prices: List[int]) -> int:
		maxProfit = 0
		currentMax = 0

		for i in reversed(prices):
		currentMax = max(currentMax, i)
		profit = currentMax - i
		maxProfit = max(profit, maxProfit)
		return maxProfit
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,101 @@
		// BFS gives TLE if we store path while traversing because whenever we find a better visit time for a word, we have to clear/make a new path vector everytime.
		// The idea is to first use BFS to search from beginWord to endWord and generate the word-to-children mapping at the same time.
		// Then, use DFS (backtracking) to generate the transformation sequences according to the mapping.
		// The reverse DFS allows us to only make the shortest paths, never having to clear a whole sequence when we encounter better result in BFS
		// No string operations are done, by dealing with indices instead.



		class Solution {
		public:
		bool able(string s,string t){
		int c=0;
		for(int i=0;i<s.length();i++)
		c+=(s[i]!=t[i]);
		return c==1;
		}
		void bfs(vector<vector<int>> &g,vector<int> parent[],int n,int start,int end){
		vector <int> dist(n,1005);
		queue <int> q;
		q.push(start);
		parent[start]={-1};
		dist[start]=0;
		while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int u:g[x]){
		if(dist[u]>dist[x]+1){
		dist[u]=dist[x]+1;
		q.push(u);
		parent[u].clear();
		parent[u].push_back(x);
		}
		else if(dist[u]==dist[x]+1)
		parent[u].push_back(x);
		}
		}
		}
		void shortestPaths(vector<vector<int>> &Paths, vector<int> &path, vector<int> parent[],int node){
		if(node==-1){
		// as parent of start was -1, we've completed the backtrack
		Paths.push_back(path);
		return ;
		}
		for(auto u:parent[node]){
		path.push_back(u);
		shortestPaths(Paths,path,parent,u);
		path.pop_back();
		}
		}
		vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
		// start and end are indices of beginWord and endWord
		int n=wordList.size(),start=-1,end=-1;
		vector<vector<string>> ANS;
		for(int i=0;i<n;i++){
		if(wordList[i]==beginWord)
		start=i;
		if(wordList[i]==endWord)
		end=i;
		}

		// if endWord doesn't exist, return empty list
		if(end==-1)
		return ANS;

		// if beginWord doesn't exist, add it in start of WordList
		if(start==-1){
		wordList.emplace(wordList.begin(),beginWord);
		start=0;
		end++;
		n++;
		}
		// for each word, we're making adjency list of neighbour words (words that can be made with one letter change)
		// Paths will store all the shortest paths (formed later by backtracking)
		vector<vector<int>> g(n,vector<int>()),Paths;

		// storing possible parents for each word (to backtrack later), path is the current sequence (while backtracking)
		vector<int> parent[n],path;

		// creating adjency list for each pair of words in the wordList (including beginword)
		for(int i=0;i<n-1;i++)
		for(int j=i+1;j<n;j++)
		if(able(wordList[i],wordList[j])){
		g[i].push_back(j);
		g[j].push_back(i);
		}

		bfs(g,parent,n,start,end);

		// backtracking to make shortestpaths
		shortestPaths(Paths,path,parent,end);
		for(auto u:Paths){
		vector <string> now;
		for(int i=0;i<u.size()-1;i++)
		now.push_back(wordList[u[i]]);
		reverse(now.begin(),now.end());
		now.push_back(wordList[end]);
		ANS.push_back(now);
		}
		return ANS;
		}
		};
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,8 @@
		class Solution {
		public:
		vector<int> runningSum(vector<int>& nums) {
		for(int i=1;i<nums.size();i++)
		nums[i]+= nums[i-1];
		return nums;
		}
		};
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,7 @@
		class Solution {
		public int[] runningSum(int[] nums) {
		for(int i=1;i<nums.length;i++)
		nums[i]+=nums[i-1];
		return nums;
		}
		}
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,30 @@
		<h2><a href="https://leetcode.com/problems/running-sum-of-1d-array/">1480. Running Sum of 1d Array</a></h2><h3>Easy</h3><hr><div><p>Given an array <code>nums</code>. We define a running sum of an array as <code>runningSum[i] = sum(nums[0]…nums[i])</code>.</p>

		<p>Return the running sum of <code>nums</code>.</p>

		<p> </p>
		<p><strong>Example 1:</strong></p>

		<pre><strong>Input:</strong> nums = [1,2,3,4]
		<strong>Output:</strong> [1,3,6,10]
		<strong>Explanation:</strong> Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].</pre>

		<p><strong>Example 2:</strong></p>

		<pre><strong>Input:</strong> nums = [1,1,1,1,1]
		<strong>Output:</strong> [1,2,3,4,5]
		<strong>Explanation:</strong> Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].</pre>

		<p><strong>Example 3:</strong></p>

		<pre><strong>Input:</strong> nums = [3,1,2,10,1]
		<strong>Output:</strong> [3,4,6,16,17]
		</pre>

		<p> </p>
		<p><strong>Constraints:</strong></p>

		<ul>
		<li><code>1 <= nums.length <= 1000</code></li>
		<li><code>-10^6 <= nums[i] <= 10^6</code></li>
		</ul></div>
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,16 @@
		class Solution {
		public int furthestBuilding(int[] heights, int bricks, int ladders) {
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for(int i=0;i<heights.length-1;i++)
		{
		int distance = heights[i+1] - heights[i];
		if(distance>0)
		pq.add(distance);
		if(pq.size()>ladders)
		bricks -= pq.poll();
		if(bricks<0)
		return i;
		}
		return heights.length-1;
		}
		}