Given `head`, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail’s `next` pointer is connected to. Note that `pos` is not passed as a parameter.

Return `true` if there is a cycle in the linked list. Otherwise, return `false`.

Example 1:

```Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
```

Example 2:

```Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
```

Example 3:

```Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
```

Constraints:

• The number of the nodes in the list is in the range `[0, 104]`.
• `-105 <= Node.val <= 105`
• `pos` is `-1` or a valid index in the linked-list.

Can you solve it using `O(1)` (i.e. constant) memory?

Idea:

Use fast and slow pointers traversal, you they can meet each other then there is a circle

Solution:

``````/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {boolean}
*/

while (fast) {
if (!fast.next) return false;
fast = fast.next.next;
slow = slow.next;
if (fast === slow) return true;
}
return false;
};``````

Given an array of positive integers `nums` and a positive integer `target`, return the minimal length of a contiguous subarray `[numsl, numsl+1, ..., numsr-1, numsr]` of which the sum is greater than or equal to `target`. If there is no such subarray, return `0` instead.

Example 1:

```Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
```

Example 2:

```Input: target = 4, nums = [1,4,4]
Output: 1
```

Example 3:

```Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
```

Constraints:

• `1 <= target <= 109`
• `1 <= nums.length <= 105`
• `1 <= nums[i] <= 105`

Idea:

Two pointers + tracking min size

Solution:

``````/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(target, nums) {
let l = 0;
let r = 0;
let ans = Infinity;
const n = nums.length;
let total = 0;
while (l < n) {
while(r < n && total < target) {
total += nums[r];
r++;
}
if (total < target) break;
ans = Math.min(ans, r - l);
total -= nums[l];
l++;
}
return ans === Infinity ? 0 : ans;
};``````

You are given an array `prices` where `prices[i]` is the price of a given stock on the `ith` day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return `0`.

Example 1:

```Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
```

Example 2:

```Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
```

Constraints:

• `1 <= prices.length <= 105`
• `0 <= prices[i] <= 104`

Idea:

Tracking two variables – minStock(min price of the stock) and maxGain(max profit)

Solution:

``````/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let maxGain = 0;
let minStock = prices[0];

for (let i = 0; i < prices.length; i++) {
minStock = Math.min(minStock, prices[i]);
maxGain = Math.max(maxGain, prices[i] - minStock);
}
return maxGain;
};``````

Given `n` non-negative integers representing an elevation map where the width of each bar is `1`, compute how much water it can trap after raining.

Example 1:

```Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
```

Example 2:

```Input: height = [4,2,0,3,2,5]
Output: 9
```

Constraints:

• `n == height.length`
• `0 <= n <= 3 * 104`
• `0 <= height[i] <= 105`

Idea:

Two pointers traversal

Solution:

``````/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
let res = 0;
const n = height.length;
let l = 0;
let r = n - 1;

while (l < r) {
let min = Math.min(height[l], height[r]);

// if left side is smaller
if (min === height[l]) {
l++;
while (l < r && height[l] < min) {
res += min - height[l++];
}
} else { // right side is smaller
r--;
while (l < r && height[r] < min) {
res += min - height[r--];
}
}
}
return res;
};``````

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

```// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}```

Example 1:

```Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = `2`, with the first two elements of `nums` being `1` and `2` respectively. It doesn't matter what you leave beyond the returned length.
```

Example 2:

```Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return length = `5`, with the first five elements of `nums` being modified to `0`, `1`, `2`, `3`, and `4` respectively. It doesn't matter what values are set beyond the returned length.
```

Constraints:

• `0 <= nums.length <= 3 * 104`
• `-104 <= nums[i] <= 104`
• `nums` is sorted in ascending order.

Solution:

``````/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
if(nums === null || nums.length === 0) return 0;
if(nums.length == 1) return 1;
var count = 0;
for(var i = 0; i < nums.length; i++) {
if(nums[i] !== nums[i+1]){
count++;
nums[count] = nums[i+1];
}
}
return count;
};``````

Given an array `nums` of n integers and an integer `target`, find three integers in `nums` such that the sum is closest to `target`. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example 1:

```Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
```

Constraints:

• `3 <= nums.length <= 10^3`
• `-10^3 <= nums[i] <= 10^3`
• `-10^4 <= target <= 10^4`

Idea:

Sorting the array + two pointers traversal

Solution:

``````/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
if (nums === null || nums.length <= 2) return null;
if (nums.length === 3) return nums[0] + nums[1] + nums[2];
// sort array first
nums.sort((a, b) => a - b);
let n = nums.length;
let res = null;
let closest = Infinity;
// two pointers traverse
for (let i = 0; i < n; i++) {
let j = i + 1;
let k = n - 1;
while (j < k) {
let sum = nums[i] + nums[j] + nums[k];
let diff = sum - target;
if (diff === 0) {
return sum;
} else if (diff > 0) {
// too large, make it smaller by moving k to the left
k--;
} else {
// get the postive diff
diff = target - sum;
// too small, make it larger by moving j to the right;
j++;
}
// keep tracking the current closest and update the current sum
if (diff < closest) {
closest = diff;
res = sum;
}
}
}
return res;
}
``````

Given an array `nums` of n integers, are there elements abc in `nums` such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Example 1:

```Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
```

Example 2:

```Input: nums = []
Output: []
```

Example 3:

```Input: nums = [0]
Output: []
```

Constraints:

• `0 <= nums.length <= 3000`
• `-105 <= nums[i] <= 105`

Idea:

• Sort nums + two pointers
• Enumerate nums[i]
• Use two pointers to find all possible sets of (i,  l,  r) such that
• i < l < r
• nums[i] + nums[l] + nums[r] === 0
• How to move pointers?
• nums[i] + nums[l] + nums[r] > 0, too large, decrease r
• nums[i] + nums[l] + nums[r] > 0, too small, increase l

Optimize:

• skip: if nums[i] > 0, then nums[i] + nums[l] + nums[r] never = 0
• skip same number: nums[i] === nums[i – 1]

Solution:

Time complexity: O(nlogn + n^2)

Space complexity: O(1)

``````/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const n = nums.length;
let res = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < n - 2; i++) {
// skip: if nums[i] > 0,
// then nums[i] + nums[l] + nums[r] never = 0
if (nums[i] > 0) break;
// skip same number
if (i > 0 && nums[i] === nums[i - 1]) continue;
let l = i + 1;
let r = n - 1;
while (l < r) {
if (nums[i] + nums[l] + nums[r] === 0) {
res.push([nums[i], nums[l++], nums[r--]]);
// skip same number
while (l < r && nums[l] === nums[l - 1]) l++;
while (l < r && nums[r] === nums[r + 1]) r--;
} else if (nums[i] + nums[l] + nums[r] > 0) {
r--;
} else {
l++;
}
}
}
return res;
};``````

Observer is a behavioral design pattern that allows some objects to notify other objects about changes in their state.

PHP has several built-in interfaces (SplSubjectSplObserver) that can be used to make your implementations of the Observer pattern compatible with the rest of the PHP code.

## Sample Code:

```<?php

namespace RefactoringGuru\Observer\Conceptual;

/**
* PHP has a couple of built-in interfaces related to the Observer pattern.
*
* Here's what the Subject interface looks like:
*
*
*     interface SplSubject
*     {
*         // Attach an observer to the subject.
*         public function attach(SplObserver \$observer);
*
*         // Detach an observer from the subject.
*         public function detach(SplObserver \$observer);
*
*         // Notify all observers about an event.
*         public function notify();
*     }
*
* There's also a built-in interface for Observers:
*
*
*     interface SplObserver
*     {
*         public function update(SplSubject \$subject);
*     }
*/

/**
* The Subject owns some important state and notifies observers when the state
* changes.
*/
class Subject implements \SplSubject
{
/**
* @var int For the sake of simplicity, the Subject's state, essential to
* all subscribers, is stored in this variable.
*/
public \$state;

/**
* @var \SplObjectStorage List of subscribers. In real life, the list of
* subscribers can be stored more comprehensively (categorized by event
* type, etc.).
*/
private \$observers;

public function __construct()
{
\$this->observers = new \SplObjectStorage();
}

/**
* The subscription management methods.
*/
public function attach(\SplObserver \$observer): void
{
echo "Subject: Attached an observer.\n";
\$this->observers->attach(\$observer);
}

public function detach(\SplObserver \$observer): void
{
\$this->observers->detach(\$observer);
echo "Subject: Detached an observer.\n";
}

/**
* Trigger an update in each subscriber.
*/
public function notify(): void
{
echo "Subject: Notifying observers...\n";
foreach (\$this->observers as \$observer) {
\$observer->update(\$this);
}
}

/**
* Usually, the subscription logic is only a fraction of what a Subject can
* really do. Subjects commonly hold some important business logic, that
* happen (or after it).
*/
{
echo "\nSubject: I'm doing something important.\n";
\$this->state = rand(0, 10);

echo "Subject: My state has just changed to: {\$this->state}\n";
\$this->notify();
}
}

/**
* Concrete Observers react to the updates issued by the Subject they had been
* attached to.
*/
class ConcreteObserverA implements \SplObserver
{
public function update(\SplSubject \$subject): void
{
if (\$subject->state < 3) {
echo "ConcreteObserverA: Reacted to the event.\n";
}
}
}

class ConcreteObserverB implements \SplObserver
{
public function update(\SplSubject \$subject): void
{
if (\$subject->state == 0 || \$subject->state >= 2) {
echo "ConcreteObserverB: Reacted to the event.\n";
}
}
}

/**
* The client code.
*/

\$subject = new Subject();

\$o1 = new ConcreteObserverA();
\$subject->attach(\$o1);

\$o2 = new ConcreteObserverB();
\$subject->attach(\$o2);

\$subject->detach(\$o2);

## Output:

```Subject: Attached an observer.
Subject: Attached an observer.

Subject: I'm doing something important.
Subject: My state has just changed to: 2
Subject: Notifying observers...
ConcreteObserverA: Reacted to the event.
ConcreteObserverB: Reacted to the event.

Subject: I'm doing something important.
Subject: My state has just changed to: 4
Subject: Notifying observers...
ConcreteObserverB: Reacted to the event.
Subject: Detached an observer.

Subject: I'm doing something important.
Subject: My state has just changed to: 1
Subject: Notifying observers...
ConcreteObserverA: Reacted to the event.```

Adapter is a structural design pattern, which allows incompatible objects to collaborate. The Adapter acts as a wrapper between two objects. It catches calls for one object and transforms them to format and interface recognizable by the second object. It is often used to make existing classes work with others without modifying their source code

Use case: It’s very often used in systems based on some legacy code. In such cases, Adapters make legacy code work with modern classes.

```<?php

/**
* The Target interface represents the interface that your application's classes
*/
{
public function send(string \$title, string \$message);
}

/**
* Here's an example of the existing class that follows the Target interface.
*
* The truth is that many real apps may not have this interface clearly defined.
* If you're in that boat, your best bet would be to extend the Adapter from one
* of your application's existing classes. If that's awkward (for instance,
* extracting an interface should be your first step.
*/
{

{
}

public function send(string \$title, string \$message): void
{
echo "Sent email with title '\$title' to '{\$this->adminEmail}' that says '\$message'.";
}
}

/**
* The Adaptee is some useful class, incompatible with the Target interface. You
* can't just go in and change the code of the class to follow the Target
* interface, since the code might be provided by a 3rd-party library.
*/
class SlackApi
{
private \$apiKey;

public function __construct(string \$login, string \$apiKey)
{
\$this->apiKey = \$apiKey;
}

{
// Send authentication request to Slack web service.
echo "Logged in to a slack account '{\$this->login}'.\n";
}

public function sendMessage(string \$chatId, string \$message): void
{
// Send message post request to Slack web service.
echo "Posted following message into the '\$chatId' chat: '\$message'.\n";
}
}

/**
* In this case, it allows the application to send notifications using Slack
* API.
*/
{
private \$slack;
private \$chatId;

public function __construct(SlackApi \$slack, string \$chatId)
{
\$this->slack = \$slack;
\$this->chatId = \$chatId;
}

/**
* An Adapter is not only capable of adapting interfaces, but it can also
* convert incoming data to the format required by the Adaptee.
*/
public function send(string \$title, string \$message): void
{
\$slackMessage = "#" . \$title . "# " . strip_tags(\$message);
\$this->slack->sendMessage(\$this->chatId, \$slackMessage);
}
}

/**
* The client code can work with any class that follows the Target interface.
*/
{
// ...

"Our website is not responding. Call admins and bring it up!");

// ...
}

echo "Client code is designed correctly and works with email notifications:\n";
echo "\n\n";

echo "The same client code can work with other classes via adapter:\n";
\$slackApi = new SlackApi("example.com", "XXXXXXXX");

## Output:

```Client code is designed correctly and works with email notifications:
Sent email with title 'Website is down!' to 'developers@example.com' that says '<strong style='color:red;font-size: 50px;'>Alert!</strong> Our website is not responding. Call admins and bring it up!'.

The same client code can work with other classes via adapter:
Logged in to a slack account 'example.com'.
Posted following message into the 'Example.com Developers' chat: '#Website is down!# Alert! Our website is not responding. Call admins and bring it up!'.```

Singleton is a creational design pattern, which ensures that only that object exists in the memory and provides a single point of access to it for any other code.

```<?php

// The Singleton class defines the `GetInstance` method
// that serves as an alternative to constructor and lets
// clients access the same instance of this class forever.
class Singleton
{
// The Singleton's instance is stored in a static field
private static \$instances = [];

// The Singleton's constructor should always be private
// to prevent direct construction calls with the `new` operator.
protected function __construct() { }

// Singletons should not be cloneable.
protected function __clone() { }

// Singletons should not be restorable from strings.
public function __wakeup()
{
throw new \Exception("Cannot unserialize a singleton.");
}

// instance.
public static function getInstance(): Singleton
{
\$cls = static::class;
if (!isset(self::\$instances[\$cls])) {
self::\$instances[\$cls] = new static();
}

return self::\$instances[\$cls];
}

// any singleton should define some business logic, which can be
// executed on its instance.
public function someFunction()
{
// ...
}
}

// testing function
function clientCode()
{
\$s1 = Singleton::getInstance();
\$s2 = Singleton::getInstance();
if (\$s1 === \$s2) {
echo "Singleton works!";
} else {
echo "Singleton failed!";
}
}

clientCode();```